# Mobile Numeric Keypad Problem: Solution in C++

Here we will understand the Mobile Numeric Keypad problem, then we will understand the solution and then write a Program in C++ to implement the solution:

GIVEN: A mobile numeric keypad as below: ### PROBLEM:

A digit is given, we have to find the number of possible numbers of given digits can be formed, using the keypad, maintaining below rules. This is the mobile numeric keypad problem.

RULES:

1. You can only press buttons that are up, left, right or down to the current button and cannot press diagonal.
2. You cannot press the * and # buttons in the keypad.

### EXAMPLE:

```For N=1, number of possible numbers would be 10 (0, 1, 2, 3, …., 9)
For N=2, number of possible numbers would be 36
Possible numbers: 00,08 11,12,14 22,21,23,25 and so on.
If we start with 0, valid numbers will be 00, 08 (count: 2)
If we start with 1, valid numbers will be 11, 12, 14 (count: 3)
If we start with 2, valid numbers will be 22, 21, 23,25 (count: 4)
If we start with 3, valid numbers will be 33, 32, 36 (count: 3)
If we start with 4, valid numbers will be 44,41,45,47 (count: 4)
If we start with 5, valid numbers will be 55,54,52,56,58 (count: 5)
………………………………
………………………………

We need to print the count of possible numbers.```

### SOLUTION:

Mobile Keypad is a rectangular grid of 4X3 (4 rows and 3 columns)
Lets say Count(i, j, N) represents the count of N length numbers starting from position (i, j).

```If N = 1
Count(i, j, N) = 10
Else
Count(i, j, N) = Sum of all Count(r, c, N-1) where (r, c) is new
position after valid move of length 1 from current
position (i, j)```

Let’s write the C++ code for the same.

### C++ program for solution of Mobile Numeric Keypad Problem:

```// Solution for mobile numeric keypad problem
#include <iostream>
using namespace std;

{'1','2','3'},
{'4','5','6'},
{'7','8','9'},
{'*','0','#'}
};

int getCount(int n) {
if(keypad == NULL || n <= 0)
return 0;

if(n == 1)
return 10;       //1 digit number 0-9

int row[] = {0, 0, -1, 0, 1};           //for up and down the row will change

int col[] = {0, -1, 0, 1, 0};           //for left and right column will change

int count[n+1];                    //store count for starting with i and length j
int move=0, rowMove=0, colMove=0, num = 0;
int nextNum=0, totalCount = 0;

for (int i=0; i<=9; i++) {                 //for length 0 and 1
count[i] = 0;
count[i] = 1;
}

for (int k=2; k<=n; k++) {                   //for digits 2 to n
for (int i=0; i<4; i++ ) {                 //for Row wise
for (int j=0; j<3; j++) {              // for column wise
if (keypad[i][j] != '*' && keypad[i][j] != '#') {   //keys are not * and #
num = keypad[i][j] - '0';                //find the number from the character
count[num][k] = 0;

for (move=0; move<5; move++) {
rowMove = i + row[move];          //move using row moving matrix
colMove = j + col[move];          //move using column moving matrix
if (rowMove >= 0 && rowMove <= 3 && colMove >=0 && colMove <= 2 &&
nextNum = keypad[rowMove][colMove] - '0';        //find next number
count[num][k] += count[nextNum][k-1];
}
}
}
}
}
}

totalCount = 0;
for (int i=0; i<=9; i++)             //for the number starting with i
totalCount += count[i][n];
}

int main() {
int n;
cout << "Number of digits: "; cin >> n;
cout << "Possible Combinations: " << getCount(n);
return 0;
}```

### OUTPUT:

```Number of digits: 4
Possible Combinations: 532```

Comment below in case you want to discuss more able the Mobile Numeric Keypad Problem.