1.
Introduction
2.
Problem Statement
2.1.
Example
3.
Approach
4.
Program
4.1.
Example
5.
Time Complexity
6.
Space Complexity
7.
Key Takeaways
Last Updated: Mar 27, 2024

Husen Kagdi
0 upvote
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems

## Introduction

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.

Also Read, Byte Array to String

## Problem Statement

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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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

### 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 optimalStay tuned for more such problems.
Thank You, and Enjoy Coding!

Guided path
Free
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems