Q51 Mobile numeric keypad | Practice | GeeksforGeeks

PHOTO EMBED

Fri Mar 31 2023 13:17:49 GMT+0000 (Coordinated Universal Time)

Saved by @Ayush_dabas07

//{ Driver Code Starts
//Initial Template for Java

import java.io.*;
import java.util.*;
class GfG
{
    public static void main(String args[])
        {
            Scanner sc = new Scanner(System.in);
            int t = sc.nextInt();
            while(t-->0)
                {
                    int n = sc.nextInt();
                    Solution ob = new Solution();
                    System.out.println(ob.getCount(n));
                }
        }
}    
// } Driver Code Ends


//User function Template for Java

class Solution
{
	public long getCount(int n)
	{
	    /*Q51 dp playlist , 
		*/
		long ans = 0;
		//make dp , keep no.of presses on rows and keypad nums on cols
		long[][] dp = new long[n+1][10];
		
		//store the info of which keypads can be pressed for which keypads
		int[][] data = {
		    {0,8},
		    {1,2,4},
            {1,2,3,5},
            {3,2,6},
            {4,1,5,7},
            {4,5,6,2,8},
            {3,6,9,5},
            {4,7,8},
            {5,7,8,9,0},
            {6,8,9}
		};
	
		//i==0 will be all 0 by default
		for(int i = 1 ; i <= n ; i++){
		    
		    for(int j = 0 ; j <= 9 ; j++){
		        
		        //if 1st row only 1 number can be created with 1 press
		        if(i==1)
		        dp[i][j] = 1;
		        
		        /* if more than 1 press add all the (i-1)th press numbers generated
		        for all numbers which can be pressed after current key stored in data[]
		        */
		        else{
		            for(int prev : data[j])
		            dp[i][j] += dp[i-1][prev];
		        }
		    }
		}
		
		//total numbers can be created with n presses will be sum of last row 
		for(int j = 0; j <= 9 ; j++)
		ans += dp[n][j];
		
		return ans;
	}
}



content_copyCOPY

https://practice.geeksforgeeks.org/problems/mobile-numeric-keypad5456/1