Table of Contents
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.
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 positionDynamic 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).