Given a mobile keypad having digits from [0-9] associated with each key, count total possible combinations of digits having length n. We can start with any digit and press only four adjacent keys of any digit. Keypad also contains * and # key which we are not allowed to press.

For example, for N = 2 the combinations are –

00, 08, 11, 12, 14, 21, 22, 23, 25, 32, 33, 36, 41, 44, 45, 47, . . . 96, 98, 99

We can use recursion to solve this problem since the problem has an optimal substructure. The problem can be broken down into smaller, simple “subproblems”, which can further be divided into yet simpler, smaller subproblems until the solution becomes trivial.

The idea is to consider each digit one by one, and count all N-digit numbers starting from current digit. For each digit i, we recurse for digit i and for all digits reachable from i. To easily find all digits reachable from any digit, we use a multimap that stores the mapping of digits reachable from every digit. When the digit becomes N-digit, we update the count.

Above solution also exhibits overlapping subproblems. As shown below, the same sub-problems (highlighted in same color) are getting computed again and again.

**N-digit number starting from 1 =**

1 + (N-1) digit number starting from 1

2 + (N-1) digit number starting from 2

4 + (N-1) digit number starting from 4

**N-digit number starting from 2 =**

1 + (N-1) digit number starting from 1

2 + (N-1) digit number starting from 2

3 + (N-1) digit number starting from 3

5 + (N-1) digit number starting from 5

**N-digit number starting from 5 =**

2 + (N-1) digit number starting from 2

4 + (N-1) digit number starting from 4

5 + (N-1) digit number starting from 5

6 + (N-1) digit number starting from 6

8 + (N-1) digit number starting from 8

We know that problems having optimal substructure and overlapping subproblems can be solved by using dynamic programming, in which subproblem solutions are *Memo*ized rather than computed again and again. The top-down *Memo*ized approach is illustrated below –

## C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 |
#include <bits/stdc++.h> using namespace std; // Maximum N-digit number allowed #define N 8 // create a lookup table to store solutions of subproblems // lookup[i][j] stores count of all numbers starting from digit i // having length n int lookup[10][N]; // Below arrays details all 4 possible movements from current cell int row[] = { 0, -1, 0, 1 }; int col[] = { -1, 0, 1, 0 }; // The function returns false if (i, j) is not a valid position int isValid(int i, int j) { // for handling '*' or '#' (present in 4th row and 1st & 3rd column) if (i == 3 && (j == 0 || j == 2)) return 0; return (i >= 0 && i <= 3 && j >= 0 && j <= 2); } // Function to fill a multimap that stores the mapping of cells // reachable from current cell void fillMap(multimap<int, int>& mp) { // mobile keypad char key[4][3] = { { '1', '2', '3' }, { '4', '5', '6' }, { '7', '8', '9' }, { '*', '0', '#' } }; // do for each row for (int i = 0; i < 4; i++) { // do for each column of row i for (int j = 0; j < 3; j++) { // move in all four possible directions of current // digit key[i][j] for (int k = 0; k < 4; k++) { int r = i + row[k]; int c = j + col[k]; // insert adjacent cell to multimap if valid if (isValid(i, j) && isValid(r, c)) mp.insert(make_pair(key[i][j] - '0', key[r][c] - '0')); } } } } // Function to count all numbers starting from digit i and // having length n int getCount(multimap<int, int> keypad, int i, int n) { if (n == 1) // reached end of digit return 1; // if sub-problem is seen for the first time, solve it and // store its result in a array if (lookup[i][n] == 0) { // recurse for digit i lookup[i][n] = getCount(keypad, i, n - 1); // recur for all digits reachable from i for (auto it = keypad.find(i); (it != keypad.end() && it->first == i); it++) lookup[i][n] += getCount(keypad, it->second, n - 1); } // return the subproblem solution return lookup[i][n]; } // main function int main() { int n = 2; // use a multimap to store mapping of cells reachable // from current cell multimap<int, int> keypad; fillMap(keypad); int count = 0; // get count of of each digit for (int i = 0; i <= 9; i++) count += getCount(keypad, i, n); cout << "Total possible combinations are " << count; return 0; } |

`Output:`

Total possible combinations are 36

The time complexity of above solution is O(n) and auxiliary space used by the program is O(n).

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply

In the sample output … 34 is not valid. It should be 36.

Thanks for bringing this up. We have updated the output. Happy coding 🙂