Hey coder. Get ready to begin a new question of dynamic programming, "Numeric Keypad".
We want you to go through the problem to understand it's outline.
Importan Link : Problem Link, Question Video Link, Solution Video Link
Hey coder. Get ready to begin a new question of dynamic programming, "Numeric Keypad".
We want you to go through the problem to understand it's outline.
Importan Link : Problem Link, Question Video Link, Solution Video Link
According to the question, since we can only press the button to the left, right, top and bottom of the current button and the current button itself, therefore, after pressing 0, we can only press {0,8}, after pressing 1, we can only press {1,2,4}, after pressing 2 we can only press {1,2,3,5}, after pressing 3 we can only press{2,3,6} and so on.
Now, we make 2D arrays for different situations.
In each cell of the following 2d arrays we store the number of words that can be obtained if the corresponding key is pressed at last.
Since N=1 and only one key can be pressed, therefore for each key only 1 word can be formed which is the number on the key itself.
This means, if we press key 1, then the one word formed is "1", if we press key 2, then the one word formed is "2", if we press 3, then the one word formed is "3" and so on.
The number of words of size 2 (as 2 buttons can be pressed) such that the button pressed at last is:
Button 1: 3 words {1-1, 2-1 and 4-1}
Button 2: 4 words {1-2, 2-2, 5-2 and 3-2}
Button 3: 3 words {2-3, 3-3 and 6-3}
Button 4: 4 words {1-4, 4-4, 5-4 and 7-4}
Button 5: 5 words {2-5, 4-5, 5-5, 6-5 and 8-5}
And so on.
The number of words of size 3 (as 3 buttons can be pressed) such that the button pressed at last is:
Button 1: 11 words i.e. the sum of words for buttons 1, 2 and 4 in N=2 i.e. 3+4+4.
We simply add button 1 to the last of all the words for buttons 1, 2 and 4 in N=2.
Button 1 {1-1-1, 2-1-1 and 4-1-1}, Button 2 {1-2-1, 2-2-1, 5-2-1 and 3-2-} and Button 4{1-4, 4-4, 5-4 and 7-4}.
Button 2: 15 words= 3+4+3+5 (refer to figure 3)
Button 3: 11 words= 4+3+4 (refer to figure 3)
Button 4: 15 words= 3+4+5+3 (refer to figure 3)
And so on.
Now, if you have understood the above explanation, we can now make a single DP array for all these values of N.
In figure, the rows represent the values of N i.e. the number of buttons that can be pressed and the columns represent all the buttons from 0-9.
At each cell we store the number of words that can be formed for the corresponding value of N such that the corresponding button is pressed at last.
And so on.
And so on.
Hence we print the sum of words of all the buttons from 0-9 for the given input N. For example, if N=2, then 2+3+4+3+4+5+4+3+5+3=36 is printed.
Reader, if you have understood the above discussion, then writing the code will be a breeze for you.
You can also refer to the code given below to check your end code.
java; true";
O(n)
O(n2)
We conclude this problem here. We hope it was clear to you.
In case you face any difficulties, we recommend you to watch the solution video.
We'll see you in the next question, goodbye.