Mobile Numeric Keypad Problem | Set 2

19 June 2025

0

Given the mobile numeric keypad. You can only press buttons that are up, left, right or down to the current button or can choose to press the same button again. Round corner buttons (i.e. * and # ) are invalid moves.

Given a number N, You have to find the distinct numbers of length N you can dial by starting from any number from 0-9, under the constraint that you can only move up, left, right or down from the last number you pressed, or you can choose to press the same button again.

Examples:

Input: N = 1
Output: 10
0, 1, 2, 3, 4, 5, 6, 7, 8 and 9 are the possible numbers.

Input: N = 2
Output: 36
All the possible numbers are 00, 08, 11, 12, 14, 21, 22, 23, 25, …

Input: N = 6
Output: 7990

Approach: We have seen many solutions to solve this problem here.

Let X_nⁱ be the count of n digit numbers ending with i.
So, by this notation,

X₁⁰ = 1 which is {0}
X₁¹ = 1 which is {1}
X₁² = 1 which is {2}
X₁³ = 1 which is {3}
and
X₂⁰ = 2 which are {00, 80}
X₂¹ = 3 which are {11, 21, 41}
X₂² = 4 which are {22, 12, 32, 52}

The central idea is, if you know X_nⁱ, what information you can get about X_{n + 1}^j

Let’s see with the help of an example:

Suppose we know, X₂¹ = 3 which are {11, 21, 41}
Because the last digit of all these numbers is 1, let’s look at the possible moves that we can have from 1:

Pressing 1 again.

Pressing 2 (moving right).

Pressing 4 (moving down)

Now we can pick any element from our set {11, 21, 41} and make any valid move:

{111, 211, 411} can be achieved with the first move.

{112, 212, 412} with the second move.

And {114, 214, 414} with the third.

We can see that making any possible move, we get the set of the same size with every move. i.e. There were 3 elements in the set of two digits numbers ending with 1, we got set of the same size(3) with every possible move from 1.

So, it can be seen that X₂¹ contributes in 3 digits numbers as follow:

X₃¹ += X₂¹
X₃² += X₂¹
X₃⁴ += X₂¹

So, in general, if we know about X_nⁱ, we know the count it contributes to X_n+1^j, where j is every possible move from i.
${X_{n+1}}^{i} = \sum {X_{n}}^{j}$
where 0<=j<=9 and from j we can have a valid to i

The idea is to first enumerate all possible directions from every given key, and maintain an array of 10 elements where the element at each index store the count of numbers ending with that index.
E.g. Initial values of array are:

Value 1 1 1 1 1 1 1 1 1 1
Index 0 1 2 3 4 5 6 7 8 9

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

How to update the array for n > 1?
Let’s enumerate all directions for all given numbers first:

From To (Possible moves)

0 0, 8

1 1, 2, 4

2 2, 1, 3, 5

3 3, 6, 2

4 4, 1, 7, 5

5 5, 4, 6, 2, 8

6 6, 3, 5, 9

7 7, 4, 8

8 8, 5, 0, 7, 9

9 9, 6, 8

From	To (Possible moves)
0	0, 8
1	1, 2, 4
2	2, 1, 3, 5
3	3, 6, 2
4	4, 1, 7, 5
5	5, 4, 6, 2, 8
6	6, 3, 5, 9
7	7, 4, 8
8	8, 5, 0, 7, 9
9	9, 6, 8

The first row of the table listed above indicates that, if the last digit in the number was zero, we can move to 0 or 8.
Let’s have a detailed look at the approach for N = 2

For N = 1, Arr[10] is {1, 1, 1, 1, 1, 1, 1, 1, 1, 1} indicating there are Arr[i] numbers ending with index i
${X_{1}}^{i} = 1 \, \, \: \: 0\leq i\leq 9$
Lets Create a new array, say Arr2[10] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
Now, for 0, possible moves are 0 and 8.
we already know
${X_{1}}^{0} = 1$
That would contribute 1 to {0, 8} i.e.
${X_{2}}^{0} += 1$
${X_{2}}^{8} += 1$
Arr2[10] = {1, 0, 0, 0, 0, 0, 0, 0, 1, 0}
For 1, Possible moves are 1, 2, 4
we already know
${X_{1}}^{1} = 1$
That would contribute 1 to {1, 2, 4} i.e.
${X_{2}}^{1} += 1$
${X_{2}}^{2} += 1$
${X_{2}}^{4} += 1$
Arr2[10] = {1, 1, 1, 0, 1, 0, 0, 0, 1, 0}
For 2, Possible moves are 2, 1, 3, 4
we already know
${X_{1}}^{2} = 1$
That would contribute 1 to {2, 1, 3, 4}
${X_{2}}^{2} += 1$
${X_{2}}^{1} += 1$
${X_{2}}^{3} += 1$
${X_{2}}^{4} += 1$
Arr2[10] = {1, 2, 2, 1, 1, 0, 0, 0, 1, 0}
and so on ….
Arr2[10] = {2, 3, 4, 3, 4, 5, 4, 3, 5, 3}
Sum = 2+3+4+3+4+5+4+3+5+3 = 36 (For N=2)
Arr2 now holds the values for ${X_{2}}^{i} \, \, \: \: 0\leq i\leq 9$ and can be considered as starting point for n=3 and the process continues.

Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <iostream>
#include <list>
using namespace std;
#define MAX 10
 
// Function to return the count of numbers possible
int getCount(int n)
{
    // Array of list storing possible direction
    // for each number from 0 to 9
    // mylist[i] stores possible moves from index i
    list<int> mylist[MAX];
 
    // Initializing list
    mylist[0].assign({ 0, 8 });
    mylist[1].assign({ 1, 2, 4 });
    mylist[2].assign({ 2, 1, 3, 5 });
    mylist[3].assign({ 3, 6, 2 });
    mylist[4].assign({ 4, 1, 7, 5 });
    mylist[5].assign({ 5, 4, 6, 2, 8 });
    mylist[6].assign({ 6, 3, 5, 9 });
    mylist[7].assign({ 7, 4, 8 });
    mylist[8].assign({ 8, 5, 0, 7, 9 });
    mylist[9].assign({ 9, 6, 8 });
 
    // Storing values for n = 1
    int Arr[MAX] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };
 
    for (int i = 2; i <= n; i++) {
 
        // To store the values for n = i
        int Arr2[MAX] = { 0 };
 
        // Loop to iterate through each index
        for (int j = 0; j < MAX; j++) {
 
            // For each move possible from j
            // Increment the value of possible
            // move positions by Arr[j]
            for (int x : mylist[j]) {
                Arr2[x] += Arr[j];
            }
        }
 
        // Update Arr[] for next iteration
        for (int j = 0; j < MAX; j++)
            Arr[j] = Arr2[j];
    }
 
    // Find the count of numbers possible
    int sum = 0;
    for (int i = 0; i < MAX; i++)
        sum += Arr[i];
 
    return sum;
}
 
// Driver code
int main()
{
    int n = 2;
 
    cout << getCount(n);
 
    return 0;
}

Java

// Java implementation of the approach
class GFG
{
    static int MAX = 10;
 
    // Function to return the count of numbers possible
    static int getCount(int n)
    {
        // Array of list storing possible direction
        // for each number from 0 to 9
        // list[i] stores possible moves from index i
         
        int [][] list = new int[MAX][];
         
        // Initializing list
        list[0] = new int [] { 0, 8 };
        list[1] = new int [] { 1, 2, 4 };
        list[2] = new int [] { 2, 1, 3, 5 };
        list[3] = new int [] { 3, 6, 2 };
        list[4] = new int [] { 4, 1, 7, 5 };
        list[5] = new int [] { 5, 4, 6, 2, 8 };
        list[6] = new int [] { 6, 3, 5, 9 };
        list[7] = new int [] { 7, 4, 8 };
        list[8] = new int [] { 8, 5, 0, 7, 9 };
        list[9] = new int [] { 9, 6, 8 };
     
        // Storing values for n = 1
        int Arr[] = new int [] { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };
     
        for (int i = 2; i <= n; i++) 
        {
     
            // To store the values for n = i
            int Arr2[] = new int [MAX];
     
            // Loop to iterate through each index
            for (int j = 0; j < MAX; j++)
            {
     
                // For each move possible from j
                // Increment the value of possible
                // move positions by Arr[j]
                for (int x = 0; x < list[j].length; x++)
                {
                    Arr2[list[j][x]] += Arr[j];
                }
            }
     
            // Update Arr[] for next iteration
            for (int j = 0; j < MAX; j++)
                Arr[j] = Arr2[j];
        }
     
        // Find the count of numbers possible
        int sum = 0;
        for (int i = 0; i < MAX; i++)
            sum += Arr[i];
     
        return sum;
    }
     
    // Driver code
    public static void main (String[] args) 
    {
     
        int n = 2;
     
        System.out.println(getCount(n));
    }
}
 
// This code is contributed by ihritik

Python3

# Python3 implementation of the approach
MAX = 10
 
# Function to return the count of numbers possible
def getCount(n):
 
    global MAX
 
    # Array of list storing possible direction
    # for each number from 0 to 9
    # mylist[i] stores possible moves from index i
    mylist = [[] for i in range(MAX)]
 
    # Initializing list
    mylist[0] = [ 0, 8 ]
    mylist[1] = [ 1, 2, 4 ]
    mylist[2] = [ 2, 1, 3, 5 ]
    mylist[3] = [ 3, 6, 2 ]
    mylist[4] = [ 4, 1, 7, 5 ]
    mylist[5] = [ 5, 4, 6, 2, 8 ]
    mylist[6] = [ 6, 3, 5, 9 ]
    mylist[7] = [ 7, 4, 8 ]
    mylist[8] = [ 8, 5, 0, 7, 9 ]
    mylist[9] = [ 9, 6, 8 ]
 
    # Storing values for n = 1
    Arr = [1 for i in range(MAX)]
 
    for i in range(2,n+1):
 
        # To store the values for n = i
        Arr2 = [0 for i in range(MAX)]
 
        # Loop to iterate through each index
        for j in range(MAX):
 
            # For each move possible from j
            # Increment the value of possible
            # move positions by Arr[j]
            for x in mylist[j]:
                Arr2[x] += Arr[j]
 
        # Update Arr[] for next iteration
        for j in range(MAX):
            Arr[j] = Arr2[j]
 
    # Find the count of numbers possible
    sum = 0
    for i in range(MAX):
        sum += Arr[i]
 
    return sum
 
# Driver code
n = 2
print(getCount(n))
 
# This code is contributed by shinjanpatra

C#

// C# implementation of the approach
using System;
 
class GFG
{
    static int MAX = 10;
 
    // Function to return the count of numbers possible
    static int getCount(int n)
    {
        // Array of list storing possible direction
        // for each number from 0 to 9
        // list[i] stores possible moves from index i
        int [][] list = new int[MAX][];
         
        // Initializing list
        list[0] = new int [] { 0, 8 };
        list[1] = new int [] { 1, 2, 4 };
        list[2] = new int [] { 2, 1, 3, 5 };
        list[3] = new int [] { 3, 6, 2 };
        list[4] = new int [] { 4, 1, 7, 5 };
        list[5] = new int [] { 5, 4, 6, 2, 8 };
        list[6] = new int [] { 6, 3, 5, 9 };
        list[7] = new int [] { 7, 4, 8 };
        list[8] = new int [] { 8, 5, 0, 7, 9 };
        list[9] = new int [] { 9, 6, 8 };
     
        // Storing values for n = 1
        int [] Arr = new int [] { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };
     
        for (int i = 2; i <= n; i++) 
        {
     
            // To store the values for n = i
            int [] Arr2 = new int [MAX];
     
            // Loop to iterate through each index
            for (int j = 0; j < MAX; j++)
            {
     
                // For each move possible from j
                // Increment the value of possible
                // move positions by Arr[j]
                for (int x = 0; x < list[j].Length; x++)
                {
                    Arr2[list[j][x]] += Arr[j];
                }
            }
     
            // Update Arr[] for next iteration
            for (int j = 0; j < MAX; j++)
                Arr[j] = Arr2[j];
        }
     
        // Find the count of numbers possible
        int sum = 0;
        for (int i = 0; i < MAX; i++)
            sum += Arr[i];
     
        return sum;
    }
     
    // Driver code
    public static void Main () 
    {
     
        int n = 2;
     
        Console.WriteLine(getCount(n));
    }
}
 
// This code is contributed by ihritik

Javascript

<script>
 
// JavaScript implementation of the approach
let MAX = 10
 
// Function to return the count of numbers possible
function getCount(n)
{
 
    // Array of list storing possible direction
    // for each number from 0 to 9
    // mylist[i] stores possible moves from index i
    let mylist = new Array(MAX).fill(new Array());
 
    // Initializing list
    mylist[0] = [ 0, 8 ];
    mylist[1] = [ 1, 2, 4 ];
    mylist[2] = [ 2, 1, 3, 5 ];
    mylist[3] = [ 3, 6, 2 ];
    mylist[4] = [ 4, 1, 7, 5 ];
    mylist[5] = [ 5, 4, 6, 2, 8 ];
    mylist[6] = [ 6, 3, 5, 9 ];
    mylist[7] = [ 7, 4, 8 ];
    mylist[8] = [ 8, 5, 0, 7, 9 ];
    mylist[9] = [ 9, 6, 8 ];
 
    // Storing values for n = 1
    let Arr = new Array(MAX).fill(1);
 
    for (let i = 2; i <= n; i++) {
 
        // To store the values for n = i
        let Arr2 = new Array(MAX).fill(0);
 
        // Loop to iterate through each index
        for (let j = 0; j < MAX; j++) {
 
            // For each move possible from j
            // Increment the value of possible
            // move positions by Arr[j]
            for (let x in mylist[j]) {
                Arr2[x] += Arr[j];
            }
        }
 
        // Update Arr[] for next iteration
        for (let j = 0; j < MAX; j++)
            Arr[j] = Arr2[j];
    }
 
    // Find the count of numbers possible
    let sum = 0;
    for (let i = 0; i < MAX; i++)
        sum += Arr[i];
 
    return sum;
}
 
// Driver code
let n = 2;
document.write(getCount(n),"</br>");
 
// This code is contributed by shinjanpatra
 
</script>

Output:

Time Complexity: O(N)
Space Complexity: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

Mobile Numeric Keypad Problem | Set 2

C++

Java

Python3

C#

Javascript

Working with Titles and Heading – Python docx Module

Creating a Receipt Calculator using Python

One Liner for Python if-elif-else Statements

LEAVE A REPLY Cancel reply

Most Popular

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

Interviewed With Kyle Smith – Founder and CEO of Escalated by Shauli Zacks

EDITOR PICKS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR POSTS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR CATEGORY

ABOUT US

FOLLOW US