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

NUMERIC KEYPAD

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

- You are given a number N, which represents the count of buttons pressed on a mobile numeric keypad.
- You can only press buttons that are up, left, right, down to the current button and the current button also.
- You cannot press bottom row corner buttons (* and #).

- You have to find the count of different numbers that can be generated by pressing N number of buttons.

WHAT

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.

- Let N=1. This denotes that one button can be pressed on the keypad.
- Let N=2. This denotes that at a time 2 buttons can be pressed on the keyboard.
- For N=3, the total number of buttons that can be pressed are 3.

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.

SINGLE DP ARRAY

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.

- As we already know, for N=0, i.e. when no button is pressed, 0 words can be formed.
- Also, if for N=1, if only one button is to be pressed, then we can form only 1 word for each button which is the number on the button itself.
- If N=2, then for:
- Button 0: 2 words=1+1 i.e. (words for button 0 in N=1 + words for button 8 in N=1)
- Button 1: 3 words=1+1+1 i.e. (words for button 1 in N=1 + words for button 2 in N=1 + words for button 4 in N=1)
- If N=3, then for:
- Button 0: 7 words=2+5 i.e. (words for button 0 in N=2 + words for button 8 in N=2)
- Button 1: 11=3+4+4 i.e. (words for button 1 in N=2 + words for button 2 in N=2 + words for button 4 in N=2)
- Button 2: 15=3+4+3+5 i.e. (words for button 1 in N=2 + words for button 2 in N=2 + words for button 3 in N=2 + words for button 5 in N=2)

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.

CODE

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.

import java.io.*;
import java.util.*;
public class Main {
public static int solution(int n) {
int[][]dp=new int[n+1][10];
int[][]data={
{0,8},
{1,2,4},
{1,2,3,5},
{2,3,6},
{1,4,5,7},
{2,4,5,6,8},
{3,5,6,9},
{4,7,8},
{5,7,8,9,0},
{6,8,9}
};
for(int i=1;i< =n;i++){
for(int j=0;j< =9;j++){
if(i==1){
dp[i][j]=1;
}else{
for(int prev:data[j]){
dp[i][j]+=dp[i-1][prev];
}
}
}
}
int sum=0;
for(int j=0;j< =9;j++){
sum+=dp[n][j];
}
return sum;
}
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
System.out.println(solution(scn.nextInt()));
}
}

java; true";

TIME COMPLEXITY-

O(n)

SPACE COMPLEXITY-

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.