Mobile Numeric Keypad Problem

Difficulty Level Hard
Frequently asked in Amazon MAQ Microsoft Sprinklr
Combinatorial Dynamic Programming Matrix StringViews 2927

Problem Statement

In the mobile numeric keypad problem, we consider a numeric keypad.  We need to find all number of possible numeric sequences of given length such that you are only allowed to press buttons which are top, down, left, and right of the current button. You are not allowed to press bottom row corner buttons ( *(star) and #(hash) ), which are marked grey in the image below.

Numeric Keypad

Example

1
10

Explanation: You can use all the digits(0 to 9), thus contributing 10 to the answer.

2
36

Explanation: Consider you choose 0, then you can choose 0 and 8 as the second number.

Consider you choose 1, then you can choose 1, 2, 4 as the second number. Similarly, we do this for all the digits.

 

Approach for mobile numeric keypad problem

Recursive Approach

For Mobile Numeric Keypad Problem, the first thing that comes to mind is a recursive approach. So, we can solve the problem recursively such that if we are at position i,j and we have n numbers to choose then we can move in upward direction(i-1,j), downward direction(i+1,j), left direction(i,j-1), right direction(i,j+1) and stay at current position(i,j) with n-1 numbers now to choose from. This approach is absolutely right but is not efficient enough.

//Base Case
if (N = 1) return 10
else
    return sum of all findNumberOfSequences(i, j, n) where i,j is new position after a valid move from current position

Dynamic Programming

When we try to solve the mobile numeric keypad problem for the length of the number sequence equal to n. We can see that the initial problem is dependent on smaller sub-problems. Consider the problem when we are solving for n equal to 3. Then we can see that our problem is dependent on the number of sequences of length equal to 2. We will then move in upward direction downward direction left direction and right direction or stay at the same place but since we took this position(digit) and added to answer. The problem has been reduced to a smaller problem with n = 2. Now if we see that we had started from a digit and moved in allowed directions then we can see that we have overlapping subproblems thus this gives us an intuition of using dynamic programming.

Generally in dynamic programming, what we do is we first solve for smaller problems and then combine the results of smaller problems to solve our initial problem so what will be doing as will be solving for n equal to 1 then n equal to 2, and so on.

Code

C++ Code

#include <bits/stdc++.h> 
using namespace std;

int findNumberOfSequences(int n) 
{ 
  char keypad[4][3] = {{'1','2','3'}, 
                       {'4','5','6'}, 
                       {'7','8','9'}, 
                       {'*','0','#'}};
  
  //Base Case
  if(n <= 0) 
    return 0; 
  if(n == 1) 
    return 10; 

  //Directions to move to
  int dir[][2]= {{0,0}, {0,-1}, {-1,0}, {0,1}, {1,0}};

  //dp[i][j] = number of sequences of length j starting with digit i
  int dp[10][n+1];
  memset(dp,0, sizeof dp);
  
  // fill the numbers starting with digit i and of length 1 
  for(int i=0; i<=9; i++)
    dp[i][1] = 1;

  // Now solve problem for n=2,3,.. using smaller sub-problems
  for(int sizeOfSequence=2; sizeOfSequence<=n; sizeOfSequence++)
  { 
    for(int row=0; row<4; row++)
    { 
      for (int col=0; col<3; col++)
      { 
        if (keypad[row][col] != '*' && keypad[row][col] != '#') 
        { 
          //fixing the first digit
          int num = keypad[row][col] - '0';

          //Now select the remaining digit in sequence
          for(int step=0; step<5; step++) 
          { 
            int new_row = row + dir[step][0]; 
            int new_col = col + dir[step][1]; 
            if(new_row>=0 && new_row<4 && new_col>=0 && new_col<3
            && keypad[new_row][new_col]!='*' && keypad[new_row][new_col]!='#') 
            { 
              int nextNum = keypad[new_row][new_col] - '0'; 
              dp[num][sizeOfSequence] += dp[nextNum][sizeOfSequence-1]; 
            } 
          } 
        } 
      } 
    } 
  } 

  // Add the number of sequences of length starting with digit i(0 to 9)
  int ans = 0; 
  for(int i=0; i<=9; i++) 
    ans += dp[i][n]; 
  return ans; 
} 

int main() 
{ 
  int t;cin>>t;
  while(t--){
    int n;cin>>n;
    cout<<"Number of sequences of length "<<n<<" = "<<findNumberOfSequences(n)<<endl;
  }
} 
5
1
2
3
4
5
Number of sequences of length 1 = 10
Number of sequences of length 2 = 36 
Number of sequences of length 3 = 138 
Number of sequences of length 4 = 532 
Number of sequences of length 5 = 2062

 

Java Code

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    
    static int findNumberOfSequences(int n) 
    { 
      	char keypad[][] = {{'1','2','3'}, 
    		           {'4','5','6'}, 
    	         	   {'7','8','9'}, 
    			   {'*','0','#'}};
      
      	//Base Case
    	if(n <= 0) 
    		return 0; 
    	if(n == 1) 
    		return 10; 
    
    	//Directions to move to
    	int dir[][]= {{0,0}, {0,-1}, {-1,0}, {0,1}, {1,0}};
    
    	//dp[i][j] = number of sequences of length j starting with digit i
    	int dp[][] = new int[10][n+1];
        
        for(int i=0;i<10;i++)
            for(int j=0;j<n+1;j++)
                dp[i][j]= 0;
                
    	// fill the numbers starting with digit i and of length 1 
    	for(int i=0; i<=9; i++)
    		dp[i][1] = 1;
    
    	// Now solve problem for n=2,3,.. using smaller sub-problems
    	for(int sizeOfSequence=2; sizeOfSequence<=n; sizeOfSequence++)
    	{ 
    		for(int row=0; row<4; row++)
    		{ 
    			for (int col=0; col<3; col++)
    			{ 
    				if (keypad[row][col] != '*' && keypad[row][col] != '#') 
    				{ 
    					//fixing the first digit
    					int num = keypad[row][col] - '0';
    
    					//Now select the remaining digit in sequence
    					for(int step=0; step<5; step++) 
    					{ 
    						int new_row = row + dir[step][0]; 
    						int new_col = col + dir[step][1]; 
    						if(new_row>=0 && new_row<4 && new_col>=0 && new_col<3
                                                && keypad[new_row][new_col]!='*' && keypad[new_row][new_col]!='#') 
    						{ 
    							int nextNum = keypad[new_row][new_col] - '0'; 
    							dp[num][sizeOfSequence] += dp[nextNum][sizeOfSequence-1]; 
    						} 
    					} 
    				} 
    			} 
    		} 
    	} 
    
      	// Add the number of sequences of length starting with digit i(0 to 9)
    	int ans = 0; 
    	for(int i=0; i<=9; i++) 
    		ans += dp[i][n]; 
    	return ans; 
    } 

    public static void main(String[] args) 
    { 
        
    	Scanner sc = new Scanner(System.in); 
    	int t = sc.nextInt(); 
    	while(t-- > 0){ 
            int n = sc.nextInt();
            int ans = findNumberOfSequences(n);
    	    System.out.println("Number of sequences of length "+n+" = "+ans);
    	}
    } 
}
5
1
2
3
4
5
Number of sequences of length 1 = 10
Number of sequences of length 2 = 36
Number of sequences of length 3 = 138
Number of sequences of length 4 = 532
Number of sequences of length 5 = 2062

Complexity Analysis

Time Complexity: O(n) for mobile numeric keypad problem

Even though we have used many nested loops but then too we consider them to run in constant time, thus we have a linear time complexity O(n) just because of the outer loop.

Space Complexity: O(n) for mobile numeric keypad problem

Since we have a 1-dimensional DP array of size n. We have a linear space complexity of O(n).

Translate »