//{ 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; } }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter