Mobile Numeric Keypad Problem - GeeksforGeeks

Mobile Numeric Keypad Problem - GeeksforGeeks
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.

N = 1 is trivial case, number of possible numbers would be 10 (0, 1, 2, 3, …., 9)
For N > 1, we need to start from some button, then move to any of the four direction (up, left, right or down) which takes to a valid button (should not go to *, #). Keep doing this until N length number is obtained (depth first traversal).

Dynamic Programming

int getCount(char keypad[][3], int n)

{

    if(keypad == NULL || n <= 0)

        return 0;

    if(n == 1)

        return 10;

    // left, up, right, down move from current location

    int row[] = {0, 0, -1, 0, 1};

    int col[] = {0, -1, 0, 1, 0};

    // taking n+1 for simplicity - count[i][j] will store

    // number count starting with digit i and length j

    int count[10][n+1];

    int i=0, j=0, k=0, move=0, ro=0, co=0, num = 0;

    int nextNum=0, totalCount = 0;

    // count numbers starting with digit i and of lengths 0 and 1

    for (i=0; i<=9; i++)

    {

        count[i][0] = 0;

        count[i][1] = 1;

    }

    // Bottom up - Get number count of length 2, 3, 4, ... , n

    for (k=2; k<=n; k++)

    {

        for (i=0; i<4; i++)  // Loop on keypad row

        {

            for (j=0; j<3; j++)   // Loop on keypad column

            {

                // Process for 0 to 9 digits

                if (keypad[i][j] != '*' && keypad[i][j] != '#')

                {

                    // Here we are counting the numbers starting with

                    // digit keypad[i][j] and of length k keypad[i][j]

                    // will become 1st digit, and we need to look for

                    // (k-1) more digits

                    num = keypad[i][j] - '0';

                    count[num][k] = 0;

 

                    // move left, up, right, down from current location

                    // and if new location is valid, then get number

                    // count of length (k-1) from that new digit and

                    // add in count we found so far

                    for (move=0; move<5; move++)

                    {

                        ro = i + row[move];

                        co = j + col[move];

                        if (ro >= 0 && ro <= 3 && co >=0 && co <= 2 &&

                           keypad[ro][co] != '*' && keypad[ro][co] != '#')

                        {

                            nextNum = keypad[ro][co] - '0';

                            count[num][k] += count[nextNum][k-1];

                        }

                    }

                }

            }

        }

    }

    // Get count of all possible numbers of length "n" starting

    // with digit 0, 1, 2, ..., 9

    totalCount = 0;

    for (i=0; i<=9; i++)

        totalCount += count[i][n];

    return totalCount;

}

Recursive Solution:

Mobile Keypad is a rectangular grid of 4X3 (4 rows and 3 columns)
Lets say Count(i, j, N) represents the count of N length numbers starting from position (i, j)

If N = 1
  Count(i, j, N) = 10  
Else
  Count(i, j, N) = Sum of all Count(r, c, N-1) where (r, c) is new 
                   position after valid move of length 1 from current 
                   position (i, j)

// left, up, right, down move from current location

int row[] = {0, 0, -1, 0, 1};

int col[] = {0, -1, 0, 1, 0}; 

// Returns count of numbers of length n starting from key position

// (i, j) in a numeric keyboard.

int getCountUtil(char keypad[][3], int i, int j, int n)

{

    if (keypad == NULL || n <= 0)

        return 0;

    // From a given key, only one number is possible of length 1

    if (n == 1)

        return 1;

    int k=0, move=0, ro=0, co=0, totalCount = 0;

    // move left, up, right, down from current location and if

    // new location is valid, then get number count of length

    // (n-1) from that new position and add in count obtained so far

    for (move=0; move<5; move++)

    {

        ro = i + row[move];

        co = j + col[move];

        if (ro >= 0 && ro <= 3 && co >=0 && co <= 2 &&

           keypad[ro][co] != '*' && keypad[ro][co] != '#')

        {

            totalCount += getCountUtil(keypad, ro, co, n-1);

        }

    }

 

    return totalCount;

}

// Return count of all possible numbers of length n in a given numeric keyboard

int getCount(char keypad[][3], int n)

{

    // Base cases

    if (keypad == NULL || n <= 0)

        return 0;

    if (n == 1)

        return 10;

     int i=0, j=0, totalCount = 0;

    for (i=0; i<4; i++)  // Loop on keypad row

    {

        for (j=0; j<3; j++)   // Loop on keypad column

        {

            // Process for 0 to 9 digits

            if (keypad[i][j] != '*' && keypad[i][j] != '#')

            {

                // Get count when number is starting from key

                // position (i, j) and add in count obtained so far

                totalCount += getCountUtil(keypad, i, j, n);

            }

        }

    }

    return totalCount;

}

Read full article from Mobile Numeric Keypad Problem - GeeksforGeeks