Generate 10-digit number using a phone keypad
Posted
by srikfreak
on Stack Overflow
See other posts from Stack Overflow
or by srikfreak
Published on 2010-05-23T21:10:55Z
Indexed on
2010/05/23
21:20 UTC
Read the original article
Hit count: 352
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.
© Stack Overflow or respective owner
