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:
- You can only press buttons that are up, left, right or down to the current button and cannot press diagonal.
- 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; char keypad[4][3] = { {'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[10][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] = 0; count[i][1] = 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 && keypad[rowMove][colMove] != '*' && keypad[rowMove][colMove] != '#') { 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]; return totalCount; } 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.