FilesExpand file tree

 master

/

MobileNumericKeypad.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

55 lines (44 loc) · 1.27 KB

 master

/

MobileNumericKeypad.java

Copy path

Top

File metadata and controls

• Code
• Blame

55 lines (44 loc) · 1.27 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

//http://www.geeksforgeeks.org/mobile-numeric-keypad-problem/

import java.util.*;

import java.lang.*;

import java.io.*;

class Codechef

{

public static void main (String[] args) throws java.lang.Exception

{

int[][] memo = new int[11][10];

for(int i = 0; i < memo.length; i++){

Arrays.fill(memo[i], -1);

}

int n = 5;

int count = 0;

List<List<Integer>> list = new ArrayList<List<Integer>>();

list.add(Arrays.asList(0,8));

list.add(Arrays.asList(1,2,4));

list.add(Arrays.asList(2,1,3,5));

list.add(Arrays.asList(3,2,6));

list.add(Arrays.asList(4,1,5,7));

list.add(Arrays.asList(5,2,4,6,8));

list.add(Arrays.asList(6,3,5,9));

list.add(Arrays.asList(7,4,8));

list.add(Arrays.asList(8,5,7,9,0));

list.add(Arrays.asList(9,6,8));

for(int i = 0; i < 10; i++){

count += solve(n,i,memo,list);

}

System.out.println(count);

}

public static int solve(int n, int digit, int[][] memo, List<List<Integer>> list){

if(memo[n][digit] != -1) return memo[n][digit];

if(n <= 1){

memo[n][digit] = 1;

return memo[n][digit];

}

int count = 0;

for(Integer i : list.get(digit)){

count += solve(n-1,i,memo,list);

}

memo[n][digit] = count;

return memo[n][digit];

}

}