Mobile Numeric Keypad Problem

Approach

Let Xni be the number of n-digit numbers that terminate in i.

As a result of this notation,

X10 = 1, which consists of  {0}.
X11 = 1, which consists of {1}.
X12 = 1, which consists of {2}.
X13 = 1, which consists of {3}.
X20 = 2, which consists of {00, 80}.
X21 = 3, which consists of  {11, 21, 41}.
X22 = 4, which consists of {22, 12, 32, 52}.

The fundamental concept is to see what information you can gain about Xn+1j if you know Xni.

Let's look at an example to see what I mean:
Assume we know that X21 = 3 equals 11, 21, and 41. Let's look at the various moves from 1 because it's the last digit in all of these numbers:

1. Pressing 1 once more.
2. Pressing the number 2 (moving right).
3. Pressing the number four (moving down)
    

We may now choose any element from our collection of 11-21-41 and make any valid move:

1. With the initial move, you can get 111, 211, and 411.
2. With the second move, 112, 212, 412.
3. And with the third, it's 114, 214, 414.

We can see that by performing any feasible move, we always end up with a set of the same size. We received a set of the same size three with every possible move from 1 because there were three items in the set of two-digit numbers ending with 1. As can be seen, X21 contributes to three-digit numbers in the following way:

X31 += X21, 
X32 += X21,
X34 += X21

So, if we know about Xni, we know how many counts it adds to Xn+1j, where ‘j’ is the number of possible moves from ‘i’.
Xn+1i Equals the sum of Xnj, where 0 <= j <=9 and we can have a valid to ‘i’ from ‘j ‘. The concept is to first enumerate all possible ways from a given key, then keep a 10-element array with the count of numbers ending with that index in each element.

E.g.

The array's initial values are:

Values: 1 1 1 1 1 1 1 1 1 1
Indexes: 0 1 2 3 4 5 6 7 8 9

And the initial result for n = 1 is the sum of all elements in the array, i.e.
1+1+1+1+1+1+1+1+1+1 = 10, there are 10 numbers of 1 digit that can be dialled.

Let us now enumerate all directions for a given number first.

Program

#include <iostream>
#include <list>
using namespace std;
#define maximum 10

long long int getCount(int n)
{
  list<long long int> ll[maximum];

  // Initialising list
  ll[0].assign({ 0, 8 });
  ll[1].assign({ 1, 2, 4 });
  ll[2].assign({ 2, 1, 3, 5 });
  ll[3].assign({ 3, 6, 2 });
  ll[4].assign({ 4, 1, 7, 5 });
  ll[5].assign({ 5, 4, 6, 2, 8 });
  ll[6].assign({ 6, 3, 5, 9 });
  ll[7].assign({ 7, 4, 8 });
  ll[8].assign({ 8, 5, 0, 7, 9 });
  ll[9].assign({ 9, 6, 8 });

  long long int v1[maximum] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };

  for (int i = 2; i <= n; i++) {

      long long int v2[maximum] = { 0 };
      for (int j = 0; j < maximum; j++) { 
          // Iterating through the list.
          for (int x : ll[j]) {
              v2[x] += v1[j];
          }
      }

      for (int j = 0; j < maximum; j++)
          v1[j] = v2[j];
  }

  long long int sum = 0;
  for (int i = 0; i < maximum; i++)
      sum += v1[i];

  return sum;
}

int main()
{
  int n;
  cin>>n;
  cout << getCount(n);
  return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Example

Input

2

Output

36

Time Complexity

O(N)
Here we are looping from  i = 2 to i = N. The value of MAX is 10, and the size of myList is also 10. So, it will take constant time to traverse. Therefore the time complexity is O(N).

Space Complexity

O(1)
The space complexity is constant as we are just declaring a list of constant size.

Check out this problem - Count Ways To Reach The Nth Stair 

Key Takeaways

In this blog, we learned about a new problem, namely the Mobile Numeric Keypad problem. We learned how to implement it in C++. We saw that the time complexity of the algorithm is O(N), which is quite optimal. Stay tuned for more such problems.
Thank You, and Enjoy Coding!