Generate 10-digit number using a phone keypad
- by srikfreak
Given a phone keypad as shown below:
1 2 3
4 5 6
7 8 9
0
How many different 10-digit numbers can be formed starting from 1? The constraint is that the movement from 1 digit to the next is similar to the movement of the Knight in a chess game.
For eg. if we are at 1 then the next digit can be either 6 or 8
if we are at 6 then the next digit can be 1, 7 or 0.
Repetition of digits are allowed - 1616161616 is a valid number.
Is there a polynomial time algorithm which solves this problem? The problem requires us to just give the count of 10-digit numbers and not necessarily list the numbers.
