Baburao was once dialing numbers from his telephone directory. He wished to find that given a number ‘N’, how many distinct ‘N’ length numbers can we make from the mobile keypad given the constraint that we can only move left, right, up, and down from the current position, or we can stay at the same position. Baburao is weak at math, so he asks the same problem to Raju and Shyam. Both analyze the problem thoroughly and then curate a solution. Let us discuss the problem statement first and implement the various approaches.

Given a number ‘N’, we need to find the count of all ‘N’ length distinct numbers such that given a position, we can only move in left, right, up, and down direction or stay at the same position on the keypad.

Example

If N = 1, then the possible one length numbers are as follows:

0 1 2 3 4 5 6 7 8 9

Therefore output = 10.

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:

Pressing 1 once more.

Pressing the number 2 (moving right).

Pressing the number four (moving down)

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

With the initial move, you can get 111, 211, and 411.

With the second move, 112, 212, 412.

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.

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.

From

To

0

0,8

1

1,2,4

2

1,2,3,5

3

2,3,6

4

1,4,5,7

5

2,4,5,6,8

6

3,5,6,9

7

4,7,8

8

5,7,8,0,9

9

6,8,9

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;
}

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.

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!