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:

mobile numeric keypad problem

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;

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.

Related Posts: