Mobile numeric keypad | Practice Medium 0 attempts
GeeksforGeeks ↗

Mobile numeric keypad | Practice

Medium Dynamic ProgrammingMemoization GeeksforGeeks

Picture a standard mobile numeric keypad (digits 0 through 9). Starting from any digit, you may press the current key again or move to the key directly above, below, left, or right of your current position — as long as it stays on the keypad — and press it. Count how many distinct N-digit numbers can be typed this way.

Input Format
Implement getCount(n). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

Input
n = 1
Output
10

Example 2

Input
n = 2
Output
36

Example 3

Input
n = 3
Output
138
Constraints
  • 1 <= N <= 25
Test Cases (3)
Case 1
Args: [1] Expected: 10
Case 2
Args: [2] Expected: 36
Case 3
Args: [3] Expected: 138
Topics
Dynamic ProgrammingMemoization

DP with Adjacency Map

javascript
function getCount(n) {
  const adj = {0:[0,8],1:[1,2,4],2:[2,1,3,5],3:[3,2,6],4:[4,1,5,7],5:[5,2,4,6,8],6:[6,3,5,9],7:[7,4,8],8:[8,5,7,9,0],9:[9,6,8]};
  let dp = Array(10).fill(1);
  for (let i = 2; i <= n; i++) {
    const next = Array(10).fill(0);
    for (let d = 0; d <= 9; d++) for (const prev of adj[d]) next[d] += dp[prev];
    dp = next;
  }
  return dp.reduce((a,b) => a+b, 0);
}

Time: O(n) | Space: O(1)

Saved in this browser only. Private to you.

JavaScript