The problem is to calculate the number of 6-digit numbers that you can create using the following scheme of things.
0-9 digits are arranged like a phone keypad.
1 2 3
4 5 6
7 8 9
0
The 6-digit number cannot start with 0. A digit can follow any other digit in the 6-digit number only if both the numbers are in the same row or column.
For eg. in a 6-digit number:
2 can follow 0
0 can follow 8
9 can follow 7
5 can follow 4
4 can follow 1
1 can follow 7
...
...
9 cannot follow 5
1 cannot follow 6
0 cannot follow 1
...
...
The idea of the solution is to use dynamic programming. A possible implementation is given below. To further optimize we can do memoization.
0-9 digits are arranged like a phone keypad.
1 2 3
4 5 6
7 8 9
0
The 6-digit number cannot start with 0. A digit can follow any other digit in the 6-digit number only if both the numbers are in the same row or column.
For eg. in a 6-digit number:
2 can follow 0
0 can follow 8
9 can follow 7
5 can follow 4
4 can follow 1
1 can follow 7
...
...
9 cannot follow 5
1 cannot follow 6
0 cannot follow 1
...
...
The idea of the solution is to use dynamic programming. A possible implementation is given below. To further optimize we can do memoization.
No comments:
Post a Comment