Problem Statement

If you have a mobile numeric keypad containing the numbers 0 to 9, as well as a positive integer N, you need to calculate the total number of combinations of length N that can be made using the keypad. A combination is a sequence of numbers that may be made by moving from one adjacent key to another (horizontally, vertically, or diagonally).

Example:

Let’s consider a mobile numeric keypad as shown below:

Suppose, if N=2, the possible combination of length 2 on this keypad would be:

(0, 0), (0, 8), (0, *)
(1, 1), (1, 2), (1, 4), (1, 6), (1, 0), (1, 8), (1, *)
(2, 2), (2, 1), (2, 3), (2, 5), (2, 0), (2, 8), (2, *)
(3, 3), (3, 2), (3, 6), (3, 0), (3, 8), (3, *)

In this scenario, there are a total of 21 potential combinations of length 2.

How can we approach the problem?

We can utilize a 2D array to keep track of the number of possibilities at each length and each keypad number in order to solve this problem using dynamic programming, which is one possible solution.

Starting with length 1, we can fill the array with keys that can be accessed from the current key and the neighbouring keys, and we can utilise the previously computed values to determine the combinations for greater lengths.

Recursive Approach

As an alternative, we could also utilise a recursive technique, where we would start at each key on the keypad and iteratively explore all potential combinations of length N starting from that key while keeping track of the count. To make the process more efficient, memorization or caching could be utilised. This is because the sub problems in this approach might overlap.

Algorithm for Mobile Numeric Keypad Problem

The algorithm for solving the mobile numeric keypad problem using dynamic programming is as follows:

Define a 2-dimensional array (table) dp[10][n+1], where dp[i][j] represents the number of sequences of length j starting with digit i.
Initialize the base cases:
- Set dp[i][1] = 1 for all digits i from 0 to 9, as there is only one way to press a single key.
Loop through the sequence length from 2 to n:
- Loop through the rows and columns of the keypad (4x3):
- For each digit in the keypad, check if it is not a '*' or '#' key:
- Fix the first digit as num = keypad[row][col] - '0'.
- Loop through the 5 possible directions to move (up, down, left, right, stay):
- Calculate the new row and column based on the current direction.
- Check if the new row and column are valid (within the keypad boundaries) and not pointing to a '*' or '#' key.
- If valid, update dp[num][sizeOfSequence] by adding dp[nextNum][sizeOfSequence-1], where nextNum is the digit at the new row and column.
After completing the loops, sum up the entries in the last column (n) of the dp array for all digits from 0 to 9, as they represent the total number of sequences of length n starting with each digit.
Return the sum as the final answer, which represents the total number of sequences of length n that can be generated using the given mobile numeric keypad.

Example in C++

Let’s take a C++ program that solves the mobile numeric keypad problem:

#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;
    }
return 0;
}

Output:

1
2
Number of sequences of length 2 = 36

Explanation:

The input is taken as t which represents the number of test cases. For each test case, the input n represents the length of the sequence of key presses, and the program outputs the number of sequences of length n that can be formed on a mobile numeric keypad using dynamic programming.

Time Complexity

The given programme has an O(n) time complexity, where n is the length of the keypress sequence. This is due to the program's use of dynamic programming, which ensures that each digit and each length of the sequence receives a fixed number of iterations.

The 4x3 keypad is iterated over by the stacked loops in a constant number of iterations, with each digit iterated over in one of five possible directions (up, down, left, right, and stay). As a result, the program's overall time complexity is proportional to the length of the sequence.

Example in Java

Let’s take a java program that solves the mobile numeric keypad problem:

import java.util.*;
public class MobileNumericKeypadProblem {


 static int[][] directions = { { 0, 0 }, { 0, -1 }, { -1, 0 }, { 0, 1 }, { 1, 0 } }; // possible directions to move to


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;


        // dp[i][j] = number of sequences of length j starting with digit i
int[][] dp = new int[10][n + 1];


        // 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 newRow = row + directions[step][0];
int newCol = col + directions[step][1];
if (newRow>= 0 &&newRow< 4 &&newCol>= 0 &&newCol< 3
&&keypad[newRow][newCol] != '*' && keypad[newRow][newCol] != '#') {
int nextNum = keypad[newRow][newCol] - '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(); // number of test cases
while (t-- > 0) {
int n = sc.nextInt(); // length of sequence
System.out.println("Number of sequences of length " + n + " = " + findNumberOfSequences(n));
        }
sc.close();
    }
}

Output:

1
2
Number of sequences of length 2 = 36

Explanation:

Because it employs the same dynamic programming technique with a fixed number of iterations for each digit and each length of the sequence, as in the C++ implementation, the time complexity of this Java programme is also O(n), where 'n' is the length of the sequence of key presses.

Time and space complexity

Time complexity

The solution to the mobile numeric keypad problem has a time complexity of O(n), where n is the length of the keypress sequence. The reason is that the method makes use of dynamic programming to create a database of size 10x(n+1), where (n+1) denotes the potential lengths of the sequences and 10 denotes the numbers on the keypad from 0 to 9. (from 1 to n). There are a total of 10x(n+1) entries in the table, and each item computes in constant time. Hence, O is the entire temporal complexity (n).

Space complexity

The solution to the mobile numeric keypad problem has a space complexity of O(n), where n is the length of the keypress sequence. This is due to the fact that the solution employs a dynamic programming methodology and necessitates the employment of a 2-dimensional array (table) with a size of 10x(n+1) to store the intermediate results. There are 10x(n+1) items in the table, and each entry occupies a fixed amount of space. Hence, O is the entire spatial complexity (n).

Data Structures Tutorial

Misc Topic: