Mobile Keypad Problem
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.
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.
First line consists of T test case. Only line of the test case consists of N.
Print the possible numbers of given length.
Input: T=3 4 5 1 Output: 532 2062 10
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.
Above possible cases are the four different direction which are connected to current number 5, similarly we will perform for all other numbers.
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):
C++ Implementation (Dynamic Programming Approach):
Output:need an explanation for this answer? contact us directly to get an explanation for this answer