Home » Interview coding problems/challenges

Mobile Keypad Problem

Solution to the mobile keypad problem: Given a number N, find out the number of possible numbers of given length.
Submitted by Divyansh Jaipuriyar, on August 18, 2020

Problem statement

Given the mobile numeric keypad. You can only press buttons that are up, left, right or down to the current button. You are not allowed to press bottom row corner buttons (i.e. * and #).

Given a number N, find out the number of possible numbers of given length.

Problem description

The problem basically needs a little bit of knowledge of mobile keypad configuration, you are required to count the different numbers that you can form with the help of certain digit that is equal to a given size, eg let N=5 then one possible number is 12345 since it has 5 digits in it. Hence with a certain algorithm, you need to develop a program that prints the total possible count of such numbers.

Input

First line consists of T test case. Only line of the test case consists of N.

Output

Print the possible numbers of given length.

Examples

Input:
T=3
4
5
1

Output:
532
2062
10

Solution Approach

1) Recursive Approach:

In this method, we will use recursion to get the total count of numbers which can be formed with a number of N lengths. We will consider digit from 0 to 9 and find all the number of N length which are possible to form. We are allowed to move in four directions from current digit so we create a Boolean function isvalid which will return whether we are in correct keypad number or not. There are two invalid keypad numbers as '*' and '#'. We will use a container which can store numbers as key and its possible connected numbers in four direction hence we will use multimap which can insert and delete in efficient time (Nlog(N)) and linear if elements are inserted in sorted order and we can find the key in (log(n)) time.

In order to get the count for each digit we will use a solve function that will return the count value, if the digit is of 1 length then it will simply return 1 otherwise we will recur for all elements which are connected to it until a single digit length is remaining.

Example:

N digit number starting from digit 5:

    5+(N-1) digit number starting from 5.
    2+(N-1) digit number starting from 2.
    6+(N-1) digit number starting from 6.
    4+(N-1) digit number starting from 4.
    8+(N-1) digit number starting from 8.

Above possible cases are the four different direction which are connected to current number 5, similarly we will perform for all other numbers.

mat[][]={{1,2,3},{4,5,6},{7,8,9},{*,0,#}} this will be the keypad.

bool isvalid(x,y):
    if invalid numbers '*' and '#':
        then return false
    if valid numbers 0-9 then return true.
	else
	return false

Time Complexity using recursion will be exponential.

2) Dynamic Programming Approach:

In this approach we will use the top-down method, we will create a dp[][] state which has numbers from digit (0-9) and each dp[i][j] has all range of numbers from 0 to j length. Initially, we will fill the dp[][] table with -1 and then calculate and fill them, if already calculated then simply return it from the dp table without calculating it again and again.

The base case for the dp approach is the same as the recursive approach apart from recursion we added memorization to make it dp.

Time complexity for the above case in the worst case is O(n*n).

Space complexity for the above case is O(n*n)

C++ Implementation (Recursive Approach):

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

//boolean function which
//return if number is in
//correct keypad position or not.
bool isvalid(ll x, ll y)
{
    //invaild numbers '*' and '#'
    if (x == 3 and (y == 0 || y == 2))
        return false;
    //valid numbers from (0-9).
    if (x >= 0 and x <= 3 and y >= 0 and y <= 2)
        return true;
    else //otherwise
        return false;
}

//possible 4 direction moves.
ll dx[] = { 0, 0, 1, -1 };
ll dy[] = { 1, -1, 0, 0 };

//build function which will create
//all digit and its possible connected
//numbers.

void build(multimap<ll, ll>& ma)
{
    //char matrix which will store
    //possible keypad numbers.
    char mat[4][3] = { { '1', '2', '3' },
        { '4', '5', '6' },
        { '7', '8', '9' },
        { '*', '0', '#' } };

    for (ll i = 0; i < 4; i++)
        for (ll j = 0; j < 3; j++) {
            //if valid position(0-9)
            if (isvalid(i, j)) {
                for (ll k = 0; k < 4; k++) {
                    //key is current position.
                    ll key = mat[i][j] - '0';
                    ll x = i + dx[k];
                    ll y = j + dy[k];
                    if (isvalid(x, y)) {
                        //val is all its valid
                        //connected numbers.
                        ll val = mat[x][y] - '0';
                        ma.insert({ key, val });
                    }
                }
            }
        }
}

//solve function which will return the
//possible n digit combination for
//each digit.
ll solve(multimap<ll, ll>& ma, ll x, ll n)
{
    //if single digit number(0-9)
    if (n == 1)
        return 1;

    //temporary variable.
    ll res = 0;
    //current number plus it recurrence
    //number with same digit.
    res += solve(ma, x, n - 1);

    //recursively call for its connected digit
    for (auto it = ma.find(x); (it != ma.end() and it->first == x); it++) {
        res += solve(ma, it->second, n - 1);
    }
    //finally return the total possible
    //combination for current number.
    return res;
}

int main()
{
    ll t;
    cout << "Enter number of test cases: ";
    cin >> t;

    while (t--) {
        cout << "Enter digit size: ";
        ll n;
        cin >> n;

        //multimap for storage of digit
        //and its connected numbers.
        multimap<ll, ll> ma;
        //call build function.
        build(ma);
        ll cnt = 0;
        for (ll i = 0; i <= 9; i++) {
            cnt += solve(ma, i, n);
        }
        cout << "Total combination of N-digit: ";
        cout << cnt << "\n";
    }

    return 0;
}

Output

Enter number of test cases: 3
Enter digit size: 2
Total combination of N-digit: 36
Enter digit size: 1
Total combination of N-digit: 10
Enter digit size: 3
Total combination of N-digit: 138

C++ Implementation (Dynamic Programming Approach):

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

//initialize dp state .
ll dp[10][1003];

//boolean function which
//return if number is in
//correct keypad position or not.
bool isvalid(ll x, ll y)
{
    //invaild numbers '*' and '#'
    if (x == 3 and (y == 0 || y == 2))
        return false;
    //valid numbers from (0-9).
    if (x >= 0 and x <= 3 and y >= 0 and y <= 2)
        return true;
    else //otherwise
        return false;
}
//possible 4 direction moves.
ll dx[] = { 0, 0, 1, -1 };
ll dy[] = { 1, -1, 0, 0 };

//build function which will create
//all digit and its possible connected
//numbers.
void build(multimap<ll, ll>& ma)
{
    //char matrix which will store
    //possible keypad numbers.
    char mat[4][3] = { { '1', '2', '3' },
        { '4', '5', '6' },
        { '7', '8', '9' },
        { '*', '0', '#' } };

    for (ll i = 0; i < 4; i++)
        for (ll j = 0; j < 3; j++) {
            //if valid position(0-9)
            if (isvalid(i, j)) {
                for (ll k = 0; k < 4; k++) {
                    //key is current position.
                    ll key = mat[i][j] - '0';
                    ll x = i + dx[k];
                    ll y = j + dy[k];
                    if (isvalid(x, y)) {
                        //val is all its valid
                        //connected numbers.
                        ll val = mat[x][y] - '0';
                        ma.insert({ key, val });
                    }
                }
            }
        }
}

//solve function which will return the
//possible n digit combination for
//each digit.
ll solve(multimap<ll, ll>& ma, ll x, ll n)
{
    //if single digit number(0-9)
    if (n == 1)
        return 1;

    //if initially calculated then return
    //without recalculating.
    if (dp[x][n] != -1)
        return dp[x][n];
    //temporary variable.
    ll res = 0;
    //current number plus it recurrence
    //number with same digit.
    res += solve(ma, x, n - 1);

    //recursively call for its connected digit
    for (auto it = ma.find(x); (it != ma.end() and it->first == x); it++) {
        res += solve(ma, it->second, n - 1);
    }
    //finally store and return the total
    //possible combination for current number.
    return dp[x][n] = res;
}

int main()
{
    ll t;
    cout << "Enter number of test cases: ";
    cin >> t;
    
    while (t--) {
        cout << "Enter digit size: ";
        ll n;
        cin >> n;

        //fill all elements of dp with -1.
        //initially for memorization.
        memset(dp, -1, sizeof(dp));
        //multimap for storage of digit
        //and its connected numbers.
        multimap<ll, ll> ma;
        //call build function.
        build(ma);
        ll cnt = 0;
        for (ll i = 0; i <= 9; i++) {
            cnt += solve(ma, i, n);
        }
        cout << "Total combination of N-digit: ";
        cout << cnt << "\n";
    }
    
    return 0;
}

Output

Enter number of test cases: 3
Enter digit size: 4
Total combination of N-digit: 532
Enter digit size: 5
Total combination of N-digit: 2062
Enter digit size: 6
Total combination of N-digit: 7990