Last Updated: 8 Jan, 2021
Mike and Mobile
Moderate
Asked in companies
Mike is a little boy who loves solving math problems. One day he was playing with his mom’s mobile. The mobile keypad contains 12 buttons { 10 digits(0-9) and 2 characters(‘*’ and ‘#’) }. Mike wants to know how many different numbers he can generate after pressing exactly the 'N' buttons on the keypad. Mike presses the buttons with the following rules:
1. He always presses the button which has a digit written on it, i.e., he never presses the ‘*’ and ‘#’ button.
2. Once he presses a button, the next button he presses should either be the same button or the button which is adjacent to the previous button.
3. In starting he can press any button except ‘*’ and ‘#’.
Mike is too little to solve this problem. Help Mike to solve this problem. As the answer can be large, so find the answer modulo 10^9 + 7.
Input format :
The first line of input contains a single integer 'T', representing the number of test cases or queries to be run.
Then the 'T' test cases follow.
The first and only line of each test case contains a positive integer N, which represents the number of buttons to press.
Output Format :
For each test case, print the number of numbers that can be generated after pressing exactly the N buttons on the keypad.
The output of each test case is printed in a separate line.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 10
1 <= N <= 5 * 10^4
Time Limit: 1 sec
Approaches
We will recursively find the different numbers we can generate after pressing N buttons on the keypad.
For simplicity, we will define the keypad with a 2D matrix.
keypad[][] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}, {-1, 0, -1}}
Below is the detailed algorithm:
Make a recursive function ‘generateNumbersHelper’ which will return the number of numbers we can generate after pressing ‘N’ buttons on the ‘KEYPAD’.
- Call the function: generateNumbersHelper('COUNT', ‘PREV’), where ‘COUNT’ denotes the number of buttons pressed and ‘PREV’ denotes the previous button pressed.
- If 'COUNT' is equal to ‘N’, return 1.
- Make a variable ‘ANS’ which stores the count of different numbers we can generate after pressing ('N' - 'COUNT') buttons on the ‘KEYPAD’. Initialise ‘ANS’ with 0.
- Check every possible button which we can press in the current state.
- Let ‘R’ denote the row of ‘PREV’ in the ‘KEYPAD’ matrix and ‘C’ denote the column of ‘PREV’ in the ‘KEYPAD’ matrix.
- There are at most 5 possibilities, { ('R', 'C'), ('R'-1, 'C'), ('R'+1, 'C'), ('R', 'C'-1), ('R', ‘C’+1)}.
- Let’s say we press the button with index ('X', ‘Y’), then ('X', 'Y') must be inside the ‘KEYPAD’ matrix and ‘KEYPAD[X][Y]’ must not be equal to -1.
- Update the ‘ANS’, ‘ANS’ += generateNumbersHelper('COUNT'+1, 'KEYPAD[X][Y]').
- Return the ‘ANS’.
In the previous approach, we are recalculating the answer. We can optimise it by storing the answers which we have calculated.
For example:
Consider the same recursive function, used in the previous approach.
Function: generateNumbersHelper('COUNT', ‘PREV’), where ‘COUNT’ denotes the number of buttons pressed and ‘PREV’ denotes the previous button pressed.
We are recalculating the answer for {(6,1) and (6,5)}.
So since there are overlapping solutions, we can store the solution which we have calculated. For this, we will make a 2D array, ‘DP’ to store the answer.
‘DP[COUNT][PREV]’ denotes the number of different numbers we can generate after pressing ('N'-count) buttons on the ‘KEYPAD’ and ‘PREV’ is ('COUNT'-1)th button that we have pressed.
Below is the detailed algorithm:
Make a recursive function ‘generateNumbersHelper’ which will return the number of numbers we can generate after pressing ‘N’ buttons on the ‘KEYPAD’.
- Make a 2D ‘DP’ array of size ‘N*10', and initialize it with -1.
- Call the function: generateNumbersHelper('COUNT', ‘PREV’), where ‘COUNT’ denotes the number of buttons pressed and ‘PREV’ denotes the previous button pressed.
- If 'COUNT' is equal to ‘N’, return 1.
- If we have visited this state, i.e, ‘DP[COUNT][PREV]’ != -1, then return ‘DP[COUNT][PREV]’.
- Make a variable ‘ANS’ which stores the count of different numbers we can generate after pressing ('N' - 'COUNT') buttons on the ‘KEYPAD’. Initialize ‘ANS’ with 0.
- Check every possible button which we can press in the current state.
- Let ‘R’ denote the row of ‘PREV’ in the ‘KEYPAD’ matrix and ‘C’ denote the column of ‘PREV’ in the ‘KEYPAD’ matrix.
- There are at most 5 possibilities, { ('R', 'C'), ('R'-1, 'C'), ('R'+1, 'C'), ('R', 'C'-1), ('R', ‘C’+1)}.
- Let’s say we press the button with index ('X', ‘Y’), then ('X', 'Y') must be inside the ‘KEYPAD’ matrix and ‘KEYPAD[X][Y]’ must not be equal to -1.
- Update the ‘ANS’, ‘ANS’ += generateNumbersHelper('COUNT'+1, 'KEYPAD[X][Y]').
- Update ‘DP[COUNT][PREV]’, ‘DP[COUNT][PREV]’ = ‘ANS’.
- Return the ‘ANS’.
Below is the detailed algorithm:
- Create a 2D array ‘DP’ of size (‘N’+1) * 10 to store the answer.
- Here, ‘DP[COUNT][PREV]’ denotes the number of different numbers we can generate after pressing ‘COUNT’ buttons on the keypad and ‘PREV’ is (‘COUNT’-1)th button that we have pressed.
- Run a loop from 0 to 9 (say iterator = ‘i’):
- Initialize ‘DP[1][i]’ = 1 (Because we will get only 1 number (which will be equal to ‘i’)).
- Initialise all other values with 0.
- Now, iterate on the indices from 2 to N (say iterator = ‘i’):
- Iterate on the digits from 0 to 9 (say iterator = ‘j’):
- Initialise ‘DP[i][j]’ with 0.
- Now iterate on the digits that are adjacent to ‘j’.
- Update ‘DP[i][j]’ :
- ‘DP[i][j]’ += ‘DP[(i-1)][X]’ (where ‘X’ denotes the digits which are adjacent to ‘j’).
- Finally, return sum of { ‘DP[N][0]’ to ‘DP[N][9’] } as the answer.
In the previous approach, we create a 2D array ‘DP’ of size (‘N’+1) * 10 to store the answer.
But, for calculating the answers for ‘DP[i][0 to 9]’, we only need values of ‘DP[i-1][0 to 9]’.
Parity of ‘i’ and (‘i-1’) will always be different i.e. if ‘i’ is odd, (‘i-1’) will be even and vice-versa. So, instead of storing the answer of ‘DP[i][j]’, we can store the answer for ‘DP[parity of i][j]’.
It means we can optimize the space by creating the ‘DP’ array of size 2 * 10.
Below is the detailed algorithm:
- Create integer array ‘DP’ of size 2 * 10.
- Run a loop from 0 to 9 (say iterator = ‘i’):
- Initialize ‘DP[1][i]’ = 1 (Because we will get only 1 number (which will be equal to ‘i’)).
- Now, iterate on the indices from 2 to N (say iterator = ‘i’):
- Iterate on the digits from 0 to 9 (say iterator = ‘j’):
- Initialise ‘DP[i%2][j]’ with 0.
- Now iterate on the digits that are adjacent to ‘j’.
- Update ‘DP[i%2][j]’ :
- ‘DP[i%2][j]’ += ‘DP[(i-1)%2][X]’ (where ‘X’ denotes the digits which are adjacent to ‘j’).
- Finally, return sum of { ‘DP[N%2][0]’ to ‘DP[N%2][9]’ } as the answer.