Given the mobile numeric keypad. You can only press buttons that are up, left, right or down to the current button. You are not allowed to press bottom row corner buttons (i.e. * and # ).
Given a number N, find out the number of possible numbers of the given length.
Examples:
For N=1, number of possible numbers would be 10 (0, 1, 2, 3, …., 9)
For N=2, number of possible numbers would be 36
Possible numbers: 00,08 11,12,14 22,21,23,25 and so on.
If we start with 0, valid numbers will be 00, 08 (count: 2)
If we start with 1, valid numbers will be 11, 12, 14 (count: 3)
If we start with 2, valid numbers will be 22, 21, 23,25 (count: 4)
If we start with 3, valid numbers will be 33, 32, 36 (count: 3)
If we start with 4, valid numbers will be 44,41,45,47 (count: 4)
If we start with 5, valid numbers will be 55,54,52,56,58 (count: 5)
....................................
....................................
We need to print the count of possible numbers.
N = 1 is trivial case, number of possible numbers would be 10 (0, 1, 2, 3, …., 9)
For N > 1, we need to start from some button, then move to any of the four direction (up, left, right or down) which takes to a valid button (should not go to *, #). Keep doing this until N length number is obtained (depth first traversal).
Recursive Solution:
Mobile Keypad is a rectangular grid of 4X3 (4 rows and 3 columns)
Lets say Count(i, j, N) represents the count of N length numbers starting from position (i, j)
If N = 1
Count(i, j, N) = 10
Else
Count(i, j, N) = Sum of all Count(r, c, N-1) where (r, c) is new
position after valid move of length 1 from current
position (i, j)
Following is the implementation of above recursive formula.
C++
// A Naive Recursive C program to count number of possible numbers// of given length#include <stdio.h>// left, up, right, down move from current locationint row[] = {0, 0, -1, 0, 1};int col[] = {0, -1, 0, 1, 0};// Returns count of numbers of length n starting from key position// (i, j) in a numeric keyboard.int getCountUtil(char keypad[][3], int i, int j, int n){ if (keypad == NULL || n <= 0) return 0; // From a given key, only one number is possible of length 1 if (n == 1) return 1; int k=0, move=0, ro=0, co=0, totalCount = 0; // move left, up, right, down from current location and if // new location is valid, then get number count of length // (n-1) from that new position and add in count obtained so far for (move=0; move<5; move++) { ro = i + row[move]; co = j + col[move]; if (ro >= 0 && ro <= 3 && co >=0 && co <= 2 && keypad[ro][co] != '*' && keypad[ro][co] != '#') { totalCount += getCountUtil(keypad, ro, co, n-1); } } return totalCount;}// Return count of all possible numbers of length n// in a given numeric keyboardint getCount(char keypad[][3], int n){ // Base cases if (keypad == NULL || n <= 0) return 0; if (n == 1) return 10; int i=0, j=0, totalCount = 0; for (i=0; i<4; i++) // Loop on keypad row { for (j=0; j<3; j++) // Loop on keypad column { // Process for 0 to 9 digits if (keypad[i][j] != '*' && keypad[i][j] != '#') { // Get count when number is starting from key // position (i, j) and add in count obtained so far totalCount += getCountUtil(keypad, i, j, n); } } } return totalCount;}// Driver program to test above functionint main(int argc, char *argv[]){ char keypad[4][3] = {{'1','2','3'}, {'4','5','6'}, {'7','8','9'}, {'*','0','#'}}; printf("Count for numbers of length %d: %dn \n", 1, getCount(keypad, 1)); printf("Count for numbers of length %d: %dn \n", 2, getCount(keypad, 2)); printf("Count for numbers of length %d: %dn \n", 3, getCount(keypad, 3)); printf("Count for numbers of length %d: %dn \n", 4, getCount(keypad, 4)); printf("Count for numbers of length %d: %dn", 5, getCount(keypad, 5)); return 0;} |
Java
// A Naive Recursive Java program // to count number of possible // numbers of given lengthimport java.util.*;import java.io.*;class GfG{// left, up, right, down // move from current locationstatic int row[] = {0, 0, -1, 0, 1};static int col[] = {0, -1, 0, 1, 0};// Returns count of numbers of length// n starting from key position// (i, j) in a numeric keyboard.static int getCountUtil(char keypad[][], int i, int j, int n){ if (keypad == null || n <= 0) return 0; // From a given key, only one // number is possible of length 1 if (n == 1) return 1; int k = 0, move = 0, ro = 0, co = 0, totalCount = 0; // move left, up, right, down // from current location and if // new location is valid, then // get number count of length // (n-1) from that new position // and add in count obtained so far for (move=0; move<5; move++) { ro = i + row[move]; co = j + col[move]; if (ro >= 0 && ro <= 3 && co >=0 && co <= 2 && keypad[ro][co] != '*' && keypad[ro][co] != '#') { totalCount += getCountUtil(keypad, ro, co, n - 1); } } return totalCount;}// Return count of all possible numbers of length n// in a given numeric keyboardstatic int getCount(char keypad[][], int n){ // Base cases if (keypad == null || n <= 0) return 0; if (n == 1) return 10; int i = 0, j = 0, totalCount = 0; for (i = 0; i < 4; i++) // Loop on keypad row { for (j=0; j<3; j++) // Loop on keypad column { // Process for 0 to 9 digits if (keypad[i][j] != '*' && keypad[i][j] != '#') { // Get count when number is starting from key // position (i, j) and add in count obtained so far totalCount += getCountUtil(keypad, i, j, n); } } } return totalCount;}// Driver codepublic static void main(String[] args) { char keypad[][] = {{'1','2','3'}, {'4','5','6'}, {'7','8','9'}, {'*','0','#'}}; System.out.printf("Count for numbers of"+ " length %d: %d", 1, getCount(keypad, 1)); System.out.printf("\nCount for numbers of" + " length %d: %d", 2, getCount(keypad, 2)); System.out.printf("\nCount for numbers of" + " length %d: %d", 3, getCount(keypad, 3)); System.out.printf("\nCount for numbers of" + " length %d: %d", 4, getCount(keypad, 4)); System.out.printf("\nCount for numbers of" + " length %d: %d", 5, getCount(keypad, 5));}}// This code has been contributed by 29AjayKumar |
Python3
# A Naive Recursive Python program to count number of possible numbers# of given length# left, up, right, down move from current locationrow = [0, 0, -1, 0, 1]col = [0, -1, 0, 1, 0]# Returns count of numbers of length n starting from key position# (i, j) in a numeric keyboard.def getCountUtil(keypad, i, j, n): if (keypad == None or n <= 0): return 0 # From a given key, only one number is possible of length 1 if (n == 1): return 1 k = 0 move = 0 ro = 0 co = 0 totalCount = 0 # move left, up, right, down from current location and if # new location is valid, then get number count of length # (n-1) from that new position and add in count obtained so far for move in range(5): ro = i + row[move] co = j + col[move] if (ro >= 0 and ro <= 3 and co >= 0 and co <= 2 and keypad[ro][co] != '*' and keypad[ro][co] != '#'): totalCount += getCountUtil(keypad, ro, co, n - 1) return totalCount# Return count of all possible numbers of length n# in a given numeric keyboarddef getCount(keypad, n): # Base cases if (keypad == None or n <= 0): return 0 if (n == 1): return 10 i = 0 j = 0 totalCount = 0 for i in range(4): # Loop on keypad row for j in range(3): # Loop on keypad column # Process for 0 to 9 digits if (keypad[i][j] != '*' and keypad[i][j] != '#'): # Get count when number is starting from key # position (i, j) and add in count obtained so far totalCount += getCountUtil(keypad, i, j, n) return totalCount# Driver codekeypad = [['1', '2', '3'], ['4', '5', '6'], ['7', '8', '9'], ['*', '0', '#']]print("Count for numbers of length 1:", getCount(keypad, 1))print("Count for numbers of length 2:", getCount(keypad, 2))print("Count for numbers of length 3:", getCount(keypad, 3))print("Count for numbers of length 4:", getCount(keypad, 4))print("Count for numbers of length 5:", getCount(keypad, 5))# This code is contributed by subhammahato348 |
C#
// A Naive Recursive C# program // to count number of possible // numbers of given lengthusing System;class GfG{// left, up, right, down // move from current locationstatic int []row = {0, 0, -1, 0, 1};static int []col = {0, -1, 0, 1, 0};// Returns count of numbers of length// n starting from key position// (i, j) in a numeric keyboard.static int getCountUtil(char [,]keypad, int i, int j, int n){ if (keypad == null || n <= 0) return 0; // From a given key, only one // number is possible of length 1 if (n == 1) return 1; int k = 0, move = 0, ro = 0, co = 0, totalCount = 0; // move left, up, right, down // from current location and if // new location is valid, then // get number count of length // (n-1) from that new position // and add in count obtained so far for (move=0; move<5; move++) { ro = i + row[move]; co = j + col[move]; if (ro >= 0 && ro <= 3 && co >=0 && co <= 2 && keypad[ro,co] != '*' && keypad[ro,co] != '#') { totalCount += getCountUtil(keypad, ro, co, n - 1); } } return totalCount;}// Return count of all possible numbers of length n// in a given numeric keyboardstatic int getCount(char [,]keypad, int n){ // Base cases if (keypad == null || n <= 0) return 0; if (n == 1) return 10; int i = 0, j = 0, totalCount = 0; for (i = 0; i < 4; i++) // Loop on keypad row { for (j = 0; j < 3; j++) // Loop on keypad column { // Process for 0 to 9 digits if (keypad[i, j] != '*' && keypad[i, j] != '#') { // Get count when number is starting from key // position (i, j) and add in count obtained so far totalCount += getCountUtil(keypad, i, j, n); } } } return totalCount;}// Driver codepublic static void Main() { char [,]keypad = {{'1','2','3'}, {'4','5','6'}, {'7','8','9'}, {'*','0','#'}}; Console.Write("Count for numbers of"+ " length {0}: {1}", 1, getCount(keypad, 1)); Console.Write("\nCount for numbers of" + "length {0}: {1}", 2, getCount(keypad, 2)); Console.Write("\nCount for numbers of" + "length {0}: {1}", 3, getCount(keypad, 3)); Console.Write("\nCount for numbers of" + "length {0}: {1}", 4, getCount(keypad, 4)); Console.Write("\nCount for numbers of" + "length {0}: {1}", 5, getCount(keypad, 5));}}/* This code contributed by PrinciRaj1992 */ |
Javascript
<script>// A Naive Recursive Javascript program// to count number of possible// numbers of given length // left, up, right, down // move from current location let row=[0, 0, -1, 0, 1]; let col=[0, -1, 0, 1, 0]; // Returns count of numbers of length // n starting from key position // (i, j) in a numeric keyboard. function getCountUtil(keypad,i,j,n) { if (keypad == null || n <= 0) {return 0;} // From a given key, only one // number is possible of length 1 if (n == 1) return 1; let k = 0, move = 0, ro = 0, co = 0, totalCount = 0; // move left, up, right, down // from current location and if // new location is valid, then // get number count of length // (n-1) from that new position // and add in count obtained so far for (move=0; move<5; move++) { ro = i + row[move]; co = j + col[move]; if (ro >= 0 && ro <= 3 && co >=0 && co <= 2 && keypad[ro][co] != '*' && keypad[ro][co] != '#') { totalCount += getCountUtil(keypad, ro, co, n - 1); } } return totalCount; } // Return count of all possible numbers of length n // in a given numeric keyboard function getCount(keypad,n) { // Base cases if (keypad == null || n <= 0) return 0; if (n == 1) return 10; let i = 0, j = 0, totalCount = 0; for (i = 0; i < 4; i++) // Loop on keypad row { for (j=0; j<3; j++) // Loop on keypad column { // Process for 0 to 9 digits if (keypad[i][j] != '*' && keypad[i][j] != '#') { // Get count when number is starting from key // position (i, j) and add in count obtained so far totalCount += getCountUtil(keypad, i, j, n); } } } return totalCount; } // Driver code let keypad=[['1','2','3'],['4','5','6'],['7','8','9'],['*','0','#']]; document.write("Count for numbers of"+ " length ", 1,": ", getCount(keypad, 1)); document.write("<br>Count for numbers of" + "length ", 2,": ", getCount(keypad, 2)); document.write("<br>Count for numbers of" + "length ", 3,": ", getCount(keypad, 3)); document.write("<br>Count for numbers of" + "length ", 4,": ", getCount(keypad, 4)); document.write("<br>Count for numbers of" + "length ", 5,": ", getCount(keypad, 5)); // This code is contributed by avanitrachhadiya2155 </script> |
PHP
<?php// A Naive Recursive PHP program // to count number of possible // numbers of given length// left, up, right, down // move from current location// static $row = array(0, 0, -1, 0, 1);//static $col = array(0, -1, 0, 1, 0);// Returns count of numbers of length// n starting from key position// (i, j) in a numeric keyboard.function getCountUtil($keypad, $i, $j, $n){ static $row= array(0,0,-1,0,1); static $col= array(0,-1,0,1,0); if ($keypad == null || $n <= 0) return 0; // From a given key, only one // number is possible of length 1 if ($n == 1) return 1; $k = 0; $move = 0; $ro = 0; $co = 0; $totalCount = 0; // move left, up, right, down // from current location and if // new location is valid, then // get number count of length // (n-1) from that new position // and add in count obtained so far for ($move = 0; $move < 5; $move++) { $ro = $i + $row[$move]; $co = $j + $col[$move]; if ($ro >= 0 && $ro <= 3 && $co >=0 && $co <= 2 && $keypad[$ro][$co] != '*' && $keypad[$ro][$co] != '#') { $totalCount += getCountUtil($keypad, $ro, $co, $n - 1); } } return $totalCount;}// Return count of all possible numbers of length n// in a given numeric keyboardfunction getCount($keypad, $n){ // Base cases if ($keypad == null || $n <= 0) return 0; if ($n == 1) return 10; $i = 0; $j = 0; $totalCount = 0; for ($i = 0; $i < 4; $i++) // Loop on keypad row { for ($j = 0; $j < 3; $j++) // Loop on keypad column { // Process for 0 to 9 digits if ($keypad[$i][$j] != '*' && $keypad[$i][$j] != '#') { // Get count when number is starting from key // position (i, j) and add in count obtained so far $totalCount += getCountUtil($keypad, $i, $j, $n); } } } return $totalCount;}// Driver code{ $keypad = array(array('1','2','3'), array('4','5','6'), array('7','8','9'), array('*','0','#')); echo("Count for numbers of"." length". getCount($keypad, 1)); echo("\nCount for numbers of" . " length ". getCount($keypad, 2)); echo("\nCount for numbers of" . " length ".getCount($keypad, 3)); echo("\nCount for numbers of" . " length ".getCount($keypad, 4)); echo("\nCount for numbers of" . " length ".getCount($keypad, 5));}// This code has been contributed by Code_Mech. |
Output
Count for numbers of length 1: 10n Count for numbers of length 2: 36n Count for numbers of length 3: 138n Count for numbers of length 4: 532n Count for numbers of length 5: 2062n
Time Complexity: O(n*m) where n and m are row and column of keypad .
Auxiliary Space: O(n*m) where n and m are row and column of keypad .
Dynamic Programming
There are many repeated traversal on smaller paths (traversal for smaller N) to find all possible longer paths (traversal for bigger N). See following two diagrams for example. In this traversal, for N = 4 from two starting positions (buttons ‘4’ and ‘8’), we can see there are few repeated traversals for N = 2 (e.g. 4 -> 1, 6 -> 3, 8 -> 9, 8 -> 7 etc).
Since the problem has both properties: Optimal Substructure and Overlapping Subproblems, it can be efficiently solved using dynamic programming.
Following is the program for dynamic programming implementation.
C++
// A Dynamic Programming based C program to count number of// possible numbers of given length#include <stdio.h>// Return count of all possible numbers of length n// in a given numeric keyboardint getCount(char keypad[][3], int n){ if(keypad == NULL || n <= 0) return 0; if(n == 1) return 10; // left, up, right, down move from current location int row[] = {0, 0, -1, 0, 1}; int col[] = {0, -1, 0, 1, 0}; // taking n+1 for simplicity - count[i][j] will store // number count starting with digit i and length j int count[10][n+1]; int i=0, j=0, k=0, move=0, ro=0, co=0, num = 0; int nextNum=0, totalCount = 0; // count numbers starting with digit i and of lengths 0 and 1 for (i=0; i<=9; i++) { count[i][0] = 0; count[i][1] = 1; } // Bottom up - Get number count of length 2, 3, 4, ... , n for (k=2; k<=n; k++) { for (i=0; i<4; i++) // Loop on keypad row { for (j=0; j<3; j++) // Loop on keypad column { // Process for 0 to 9 digits if (keypad[i][j] != '*' && keypad[i][j] != '#') { // Here we are counting the numbers starting with // digit keypad[i][j] and of length k keypad[i][j] // will become 1st digit, and we need to look for // (k-1) more digits num = keypad[i][j] - '0'; count[num][k] = 0; // move left, up, right, down from current location // and if new location is valid, then get number // count of length (k-1) from that new digit and // add in count we found so far for (move=0; move<5; move++) { ro = i + row[move]; co = j + col[move]; if (ro >= 0 && ro <= 3 && co >=0 && co <= 2 && keypad[ro][co] != '*' && keypad[ro][co] != '#') { nextNum = keypad[ro][co] - '0'; count[num][k] += count[nextNum][k-1]; } } } } } } // Get count of all possible numbers of length "n" starting // with digit 0, 1, 2, ..., 9 totalCount = 0; for (i=0; i<=9; i++) totalCount += count[i][n]; return totalCount;}// Driver program to test above functionint main(int argc, char *argv[]){ char keypad[4][3] = {{'1','2','3'}, {'4','5','6'}, {'7','8','9'}, {'*','0','#'}}; printf("Count for numbers of length %d: %dn", 1, getCount(keypad, 1)); printf("\nCount for numbers of length %d: %dn", 2, getCount(keypad, 2)); printf("\nCount for numbers of length %d: %dn", 3, getCount(keypad, 3)); printf("\nCount for numbers of length %d: %dn", 4, getCount(keypad, 4)); printf("\nCount for numbers of length %d: %dn", 5, getCount(keypad, 5)); return 0;} |
Java
// A Dynamic Programming based Java program to // count number of possible numbers of given lengthimport java.util.*;import java.io.*;class GFG{ // Return count of all possible numbers of length n// in a given numeric keyboardstatic int getCount(char keypad[][], int n){ if(keypad == null || n <= 0) return 0; if(n == 1) return 10; // left, up, right, down move from current location int row[] = {0, 0, -1, 0, 1}; int col[] = {0, -1, 0, 1, 0}; // taking n+1 for simplicity - count[i][j] will store // number count starting with digit i and length j int [][]count = new int[10][n + 1]; int i = 0, j = 0, k = 0, move = 0, ro = 0, co = 0, num = 0; int nextNum = 0, totalCount = 0; // count numbers starting with digit i // and of lengths 0 and 1 for (i = 0; i <= 9; i++) { count[i][0] = 0; count[i][1] = 1; } // Bottom up - Get number count of length 2, 3, 4, ... , n for (k = 2; k <= n; k++) { for (i = 0; i < 4; i++) // Loop on keypad row { for (j = 0; j < 3; j++) // Loop on keypad column { // Process for 0 to 9 digits if (keypad[i][j] != '*' && keypad[i][j] != '#') { // Here we are counting the numbers starting with // digit keypad[i][j] and of length k keypad[i][j] // will become 1st digit, and we need to look for // (k-1) more digits num = keypad[i][j] - '0'; count[num][k] = 0; // move left, up, right, down from current location // and if new location is valid, then get number // count of length (k-1) from that new digit and // add in count we found so far for (move = 0; move < 5; move++) { ro = i + row[move]; co = j + col[move]; if (ro >= 0 && ro <= 3 && co >= 0 && co <= 2 && keypad[ro][co] != '*' && keypad[ro][co] != '#') { nextNum = keypad[ro][co] - '0'; count[num][k] += count[nextNum][k - 1]; } } } } } } // Get count of all possible numbers of length "n" // starting with digit 0, 1, 2, ..., 9 totalCount = 0; for (i = 0; i <= 9; i++) totalCount += count[i][n]; return totalCount;}// Driver Codepublic static void main(String[] args){ char keypad[][] = {{'1','2','3'}, {'4','5','6'}, {'7','8','9'}, {'*','0','#'}}; System.out.printf("Count for numbers of length %d: %d\n", 1, getCount(keypad, 1)); System.out.printf("Count for numbers of length %d: %d\n", 2, getCount(keypad, 2)); System.out.printf("Count for numbers of length %d: %d\n", 3, getCount(keypad, 3)); System.out.printf("Count for numbers of length %d: %d\n", 4, getCount(keypad, 4)); System.out.printf("Count for numbers of length %d: %d\n", 5, getCount(keypad, 5));}}// This code is contributed by Rajput-Ji |
Python3
# A Dynamic Programming based C program to count number of# possible numbers of given length# Return count of all possible numbers of length n# in a given numeric keyboarddef getCount(keypad, n): if (keypad == None or n <= 0): return 0 if (n == 1): return 10 # left, up, right, down move from current location row = [0, 0, -1, 0, 1] col = [0, -1, 0, 1, 0] # taking n+1 for simplicity - count[i][j] will store # number count starting with digit i and length j # count[10][n+1] count = [[0]*(n + 1)]*10 i = 0 j = 0 k = 0 move = 0 ro = 0 co = 0 num = 0 nextNum = 0 totalCount = 0 # count numbers starting with # digit i and of lengths 0 and 1 for i in range(10): count[i][0] = 0 count[i][1] = 1 # Bottom up - Get number # count of length 2, 3, 4, ... , n for k in range(2, n + 1): for i in range(4): # Loop on keypad row for j in range(3): # Loop on keypad column # Process for 0 to 9 digits if (keypad[i][j] != '*' and keypad[i][j] != '#'): # Here we are counting the numbers starting with # digit keypad[i][j] and of length k keypad[i][j] # will become 1st digit, and we need to look for # (k-1) more digits num = ord(keypad[i][j]) - 48 count[num][k] = 0 # move left, up, right, down from current location # and if new location is valid, then get number # count of length (k-1) from that new digit and # add in count we found so far for move in range(5): ro = i + row[move] co = j + col[move] if (ro >= 0 and ro <= 3 and co >= 0 and co <= 2 and keypad[ro][co] != '*' and keypad[ro][co] != '#'): nextNum = ord(keypad[ro][co]) - 48 count[num][k] += count[nextNum][k - 1] # Get count of all possible numbers of length "n" starting # with digit 0, 1, 2, ..., 9 totalCount = 0 for i in range(10): totalCount += count[i][n] return totalCount# Driver codeif __name__ == "__main__": keypad = [['1','2','3'], ['4','5','6'], ['7','8','9'], ['*','0','#']] print("Count for numbers of length", 1, ":", getCount(keypad, 1)) print("Count for numbers of length", 2, ":", getCount(keypad, 2)) print("Count for numbers of length", 3, ":", getCount(keypad, 3)) print("Count for numbers of length", 4, ":", getCount(keypad, 4)) print("Count for numbers of length", 5, ":", getCount(keypad, 5)) # This code is contributed by subhammahato348 |
C#
// A Dynamic Programming based C# program to // count number of possible numbers of given Lengthusing System;class GFG{ // Return count of all possible numbers of Length n// in a given numeric keyboardstatic int getCount(char [,]keypad, int n){ if(keypad == null || n <= 0) return 0; if(n == 1) return 10; // left, up, right, down move // from current location int []row = {0, 0, -1, 0, 1}; int []col = {0, -1, 0, 1, 0}; // taking n+1 for simplicity - count[i,j] // will store number count starting with // digit i and.Length j int [,]count = new int[10,n + 1]; int i = 0, j = 0, k = 0, move = 0, ro = 0, co = 0, num = 0; int nextNum = 0, totalCount = 0; // count numbers starting with digit i // and of.Lengths 0 and 1 for (i = 0; i <= 9; i++) { count[i, 0] = 0; count[i, 1] = 1; } // Bottom up - Get number count of // Length 2, 3, 4, ... , n for (k = 2; k <= n; k++) { for (i = 0; i < 4; i++) // Loop on keypad row { for (j = 0; j < 3; j++) // Loop on keypad column { // Process for 0 to 9 digits if (keypad[i, j] != '*' && keypad[i, j] != '#') { // Here we are counting the numbers starting with // digit keypad[i,j] and of.Length k keypad[i,j] // will become 1st digit, and we need to look for // (k-1) more digits num = keypad[i, j] - '0'; count[num, k] = 0; // move left, up, right, down from current location // and if new location is valid, then get number // count of.Length (k-1) from that new digit and //.Add in count we found so far for (move = 0; move < 5; move++) { ro = i + row[move]; co = j + col[move]; if (ro >= 0 && ro <= 3 && co >= 0 && co <= 2 && keypad[ro, co] != '*' && keypad[ro, co] != '#') { nextNum = keypad[ro, co] - '0'; count[num, k] += count[nextNum, k - 1]; } } } } } } // Get count of all possible numbers of.Length "n" // starting with digit 0, 1, 2, ..., 9 totalCount = 0; for (i = 0; i <= 9; i++) totalCount += count[i, n]; return totalCount;}// Driver Codepublic static void Main(String[] args){ char [,]keypad = {{'1', '2', '3'}, {'4', '5', '6'}, {'7', '8', '9'}, {'*', '0', '#'}}; Console.Write("Count for numbers of.Length {0}: {1}\n", 1, getCount(keypad, 1)); Console.Write("Count for numbers of.Length {0}: {1}\n", 2, getCount(keypad, 2)); Console.Write("Count for numbers of.Length {0}: {1}\n", 3, getCount(keypad, 3)); Console.Write("Count for numbers of.Length {0}: {1}\n", 4, getCount(keypad, 4)); Console.Write("Count for numbers of.Length {0}: {1}\n", 5, getCount(keypad, 5));}}// This code is contributed by Rajput-Ji |
Javascript
<script>// A Dynamic Programming based Javascript program to// count number of possible numbers of given length// Return count of all possible numbers of length n// in a given numeric keyboardfunction getCount(keypad, n){ if (keypad == null || n <= 0) return 0; if (n == 1) return 10; // left, up, right, down move // from current location let row = [ 0, 0, -1, 0, 1 ]; let col = [ 0, -1, 0, 1, 0 ]; // Taking n+1 for simplicity - count[i][j] // will store number count starting with // digit i and length j let count = new Array(10); for(let i = 0; i < 10; i++) { count[i] = new Array(n + 1); for(let j = 0; j < n + 1; j++) { count[i][j] = 0; } } let i = 0, j = 0, k = 0, move = 0, ro = 0, co = 0, num = 0; let nextNum = 0, totalCount = 0; // count numbers starting with digit i // and of lengths 0 and 1 for(i = 0; i <= 9; i++) { count[i][0] = 0; count[i][1] = 1; } // Bottom up - Get number count // of length 2, 3, 4, ... , n for(k = 2; k <= n; k++) { // Loop on keypad row for(i = 0; i < 4; i++) { // Loop on keypad column for(j = 0; j < 3; j++) { // Process for 0 to 9 digits if (keypad[i][j] != '*' && keypad[i][j] != '#') { // Here we are counting the numbers starting with // digit keypad[i][j] and of length k keypad[i][j] // will become 1st digit, and we need to look for // (k-1) more digits num = keypad[i][j].charCodeAt(0) - '0'.charCodeAt(0); count[num][k] = 0; // Move left, up, right, down from current location // and if new location is valid, then get number // count of length (k-1) from that new digit and // add in count we found so far for(move = 0; move < 5; move++) { ro = i + row[move]; co = j + col[move]; if (ro >= 0 && ro <= 3 && co >= 0 && co <= 2 && keypad[ro][co] != '*' && keypad[ro][co] != '#') { nextNum = keypad[ro][co].charCodeAt(0) - '0'.charCodeAt(0); count[num][k] += count[nextNum][k - 1]; } } } } } } // Get count of all possible numbers of length "n" // starting with digit 0, 1, 2, ..., 9 totalCount = 0; for(i = 0; i <= 9; i++) totalCount += count[i][n]; return totalCount; }// Driver Codelet keypad = [ [ '1','2','3' ], [ '4','5','6' ], [ '7','8','9' ], [ '*','0','#' ] ]; document.write("Count for numbers of length " + 1 + " : " + getCount(keypad, 1) + "<br>")document.write("Count for numbers of length " + 2 + " : " + getCount(keypad, 2) + "<br>")document.write("Count for numbers of length " + 3 + " : " + getCount(keypad, 3) + "<br>")document.write("Count for numbers of length " + 4 + " : " + getCount(keypad, 4) + "<br>")document.write("Count for numbers of length " + 5 + " : " + getCount(keypad, 5) + "<br>")// This code is contributed by rag2127</script> |
Output
Count for numbers of length 1: 10n Count for numbers of length 2: 36n Count for numbers of length 3: 138n Count for numbers of length 4: 532n Count for numbers of length 5: 2062n
A Space Optimized Solution:
The above dynamic programming approach also runs in O(n) time and requires O(n) auxiliary space, as only one for loop runs n times, other for loops runs for constant time. We can see that nth iteration needs data from (n-1)th iteration only, so we need not keep the data from older iterations. We can have a space efficient dynamic programming approach with just two arrays of size 10. Thanks to Nik for suggesting this solution.
C++
// A Space Optimized C++ program to count number of possible numbers// of given length#include <bits/stdc++.h>using namespace std;// Return count of all possible numbers of length n// in a given numeric keyboardint getCount(char keypad[][3], int n){ if (keypad == NULL || n <= 0) return 0; if (n == 1) return 10; // odd[i], even[i] arrays represent count of numbers starting // with digit i for any length j int odd[10], even[10]; int i = 0, j = 0, useOdd = 0, totalCount = 0; for (i = 0; i <= 9; i++) odd[i] = 1; // for j = 1 for (j = 2; j <= n; j++) // Bottom Up calculation from j = 2 to n { useOdd = 1 - useOdd; // Here we are explicitly writing lines for each number 0 // to 9. But it can always be written as DFS on 4X3 grid // using row, column array valid moves if (useOdd == 1) { even[0] = odd[0] + odd[8]; even[1] = odd[1] + odd[2] + odd[4]; even[2] = odd[2] + odd[1] + odd[3] + odd[5]; even[3] = odd[3] + odd[2] + odd[6]; even[4] = odd[4] + odd[1] + odd[5] + odd[7]; even[5] = odd[5] + odd[2] + odd[4] + odd[8] + odd[6]; even[6] = odd[6] + odd[3] + odd[5] + odd[9]; even[7] = odd[7] + odd[4] + odd[8]; even[8] = odd[8] + odd[0] + odd[5] + odd[7] + odd[9]; even[9] = odd[9] + odd[6] + odd[8]; } else { odd[0] = even[0] + even[8]; odd[1] = even[1] + even[2] + even[4]; odd[2] = even[2] + even[1] + even[3] + even[5]; odd[3] = even[3] + even[2] + even[6]; odd[4] = even[4] + even[1] + even[5] + even[7]; odd[5] = even[5] + even[2] + even[4] + even[8] + even[6]; odd[6] = even[6] + even[3] + even[5] + even[9]; odd[7] = even[7] + even[4] + even[8]; odd[8] = even[8] + even[0] + even[5] + even[7] + even[9]; odd[9] = even[9] + even[6] + even[8]; } } // Get count of all possible numbers of length "n" starting // with digit 0, 1, 2, ..., 9 totalCount = 0; if (useOdd == 1) { for (i = 0; i <= 9; i++) totalCount += even[i]; } else { for (i = 0; i <= 9; i++) totalCount += odd[i]; } return totalCount;}// Driver program to test above functionint main(){ char keypad[4][3] = {{'1', '2', '3'}, {'4', '5', '6'}, {'7', '8', '9'}, {'*', '0', '#'}}; cout << "Count for numbers of length 1: " << getCount(keypad, 1) << endl; cout << "Count for numbers of length 2: " << getCount(keypad, 2) << endl; cout << "Count for numbers of length 3: " << getCount(keypad, 3) << endl; cout << "Count for numbers of length 4: " << getCount(keypad, 4) << endl; cout << "Count for numbers of length 5: " << getCount(keypad, 5) << endl; return 0;}//This code is contributed by Mayank Tyagi |
C
// A Space Optimized C program to count number of possible numbers// of given length#include <stdio.h>// Return count of all possible numbers of length n// in a given numeric keyboardint getCount(char keypad[][3], int n){ if(keypad == NULL || n <= 0) return 0; if(n == 1) return 10; // odd[i], even[i] arrays represent count of numbers starting // with digit i for any length j int odd[10], even[10]; int i = 0, j = 0, useOdd = 0, totalCount = 0; for (i=0; i<=9; i++) odd[i] = 1; // for j = 1 for (j=2; j<=n; j++) // Bottom Up calculation from j = 2 to n { useOdd = 1 - useOdd; // Here we are explicitly writing lines for each number 0 // to 9. But it can always be written as DFS on 4X3 grid // using row, column array valid moves if(useOdd == 1) { even[0] = odd[0] + odd[8]; even[1] = odd[1] + odd[2] + odd[4]; even[2] = odd[2] + odd[1] + odd[3] + odd[5]; even[3] = odd[3] + odd[2] + odd[6]; even[4] = odd[4] + odd[1] + odd[5] + odd[7]; even[5] = odd[5] + odd[2] + odd[4] + odd[8] + odd[6]; even[6] = odd[6] + odd[3] + odd[5] + odd[9]; even[7] = odd[7] + odd[4] + odd[8]; even[8] = odd[8] + odd[0] + odd[5] + odd[7] + odd[9]; even[9] = odd[9] + odd[6] + odd[8]; } else { odd[0] = even[0] + even[8]; odd[1] = even[1] + even[2] + even[4]; odd[2] = even[2] + even[1] + even[3] + even[5]; odd[3] = even[3] + even[2] + even[6]; odd[4] = even[4] + even[1] + even[5] + even[7]; odd[5] = even[5] + even[2] + even[4] + even[8] + even[6]; odd[6] = even[6] + even[3] + even[5] + even[9]; odd[7] = even[7] + even[4] + even[8]; odd[8] = even[8] + even[0] + even[5] + even[7] + even[9]; odd[9] = even[9] + even[6] + even[8]; } } // Get count of all possible numbers of length "n" starting // with digit 0, 1, 2, ..., 9 totalCount = 0; if(useOdd == 1) { for (i=0; i<=9; i++) totalCount += even[i]; } else { for (i=0; i<=9; i++) totalCount += odd[i]; } return totalCount;}// Driver program to test above functionint main(){ char keypad[4][3] = {{'1','2','3'}, {'4','5','6'}, {'7','8','9'}, {'*','0','#'} }; printf("Count for numbers of length %d: %dn", 1, getCount(keypad, 1)); printf("Count for numbers of length %d: %dn", 2, getCount(keypad, 2)); printf("Count for numbers of length %d: %dn", 3, getCount(keypad, 3)); printf("Count for numbers of length %d: %dn", 4, getCount(keypad, 4)); printf("Count for numbers of length %d: %dn", 5, getCount(keypad, 5)); return 0;} |
Java
// A Space Optimized Java program to // count number of possible numbers // of given lengthimport java.util.*;import java.io.*;class GFG {// Return count of all possible numbers of // length n in a given numeric keyboardstatic int getCount(char keypad[][], int n){ if(keypad == null || n <= 0) return 0; if(n == 1) return 10; // odd[i], even[i] arrays represent count of // numbers starting with digit i for any length j int []odd = new int[10]; int []even = new int[10]; int i = 0, j = 0, useOdd = 0, totalCount = 0; for (i = 0; i <= 9; i++) odd[i] = 1; // for j = 1 // Bottom Up calculation from j = 2 to n for (j = 2; j <= n; j++) { useOdd = 1 - useOdd; // Here we are explicitly writing lines // for each number 0 to 9. But it can always be // written as DFS on 4X3 grid using row, // column array valid moves if(useOdd == 1) { even[0] = odd[0] + odd[8]; even[1] = odd[1] + odd[2] + odd[4]; even[2] = odd[2] + odd[1] + odd[3] + odd[5]; even[3] = odd[3] + odd[2] + odd[6]; even[4] = odd[4] + odd[1] + odd[5] + odd[7]; even[5] = odd[5] + odd[2] + odd[4] + odd[8] + odd[6]; even[6] = odd[6] + odd[3] + odd[5] + odd[9]; even[7] = odd[7] + odd[4] + odd[8]; even[8] = odd[8] + odd[0] + odd[5] + odd[7] + odd[9]; even[9] = odd[9] + odd[6] + odd[8]; } else { odd[0] = even[0] + even[8]; odd[1] = even[1] + even[2] + even[4]; odd[2] = even[2] + even[1] + even[3] + even[5]; odd[3] = even[3] + even[2] + even[6]; odd[4] = even[4] + even[1] + even[5] + even[7]; odd[5] = even[5] + even[2] + even[4] + even[8] + even[6]; odd[6] = even[6] + even[3] + even[5] + even[9]; odd[7] = even[7] + even[4] + even[8]; odd[8] = even[8] + even[0] + even[5] + even[7] + even[9]; odd[9] = even[9] + even[6] + even[8]; } } // Get count of all possible numbers of // length "n" starting with digit 0, 1, 2, ..., 9 totalCount = 0; if(useOdd == 1) { for (i = 0; i <= 9; i++) totalCount += even[i]; } else { for (i = 0; i <= 9; i++) totalCount += odd[i]; } return totalCount;}// Driver Codepublic static void main(String[] args) { char keypad[][] = {{'1','2','3'}, {'4','5','6'}, {'7','8','9'}, {'*','0','#'}}; System.out.printf("Count for numbers of length %d: %d\n", 1, getCount(keypad, 1)); System.out.printf("Count for numbers of length %d: %d\n", 2, getCount(keypad, 2)); System.out.printf("Count for numbers of length %d: %d\n", 3, getCount(keypad, 3)); System.out.printf("Count for numbers of length %d: %d\n", 4, getCount(keypad, 4)); System.out.printf("Count for numbers of length %d: %d\n", 5, getCount(keypad, 5));}}// This code is contributed by PrinciRaj1992 |
Python3
# A Space Optimized Python program to count # number of possible numbers# of given length# Return count of all possible numbers # of length n# in a given numeric keyboarddef getCount(keypad, n): if(not keypad or n <= 0): return 0 if(n == 1): return 10 # odd[i], even[i] arrays represent # count of numbers starting # with digit i for any length j odd = [0]*10 even = [0]*10 i = 0 j = 0 useOdd = 0 totalCount = 0 for i in range(10): odd[i] = 1 # for j = 1 for j in range(2,n+1): # Bottom Up calculation from j = 2 to n useOdd = 1 - useOdd # Here we are explicitly writing lines for each number 0 # to 9. But it can always be written as DFS on 4X3 grid # using row, column array valid moves if(useOdd == 1): even[0] = odd[0] + odd[8] even[1] = odd[1] + odd[2] + odd[4] even[2] = odd[2] + odd[1] + odd[3] + odd[5] even[3] = odd[3] + odd[2] + odd[6] even[4] = odd[4] + odd[1] + odd[5] + odd[7] even[5] = odd[5] + odd[2] + odd[4] + odd[8] + odd[6] even[6] = odd[6] + odd[3] + odd[5] + odd[9] even[7] = odd[7] + odd[4] + odd[8] even[8] = odd[8] + odd[0] + odd[5] + odd[7] + odd[9] even[9] = odd[9] + odd[6] + odd[8] else: odd[0] = even[0] + even[8] odd[1] = even[1] + even[2] + even[4] odd[2] = even[2] + even[1] + even[3] + even[5] odd[3] = even[3] + even[2] + even[6] odd[4] = even[4] + even[1] + even[5] + even[7] odd[5] = even[5] + even[2] + even[4] + even[8] + even[6] odd[6] = even[6] + even[3] + even[5] + even[9] odd[7] = even[7] + even[4] + even[8] odd[8] = even[8] + even[0] + even[5] + even[7] + even[9] odd[9] = even[9] + even[6] + even[8] # Get count of all possible numbers of length "n" starting # with digit 0, 1, 2, ..., 9 totalCount = 0 if(useOdd == 1): for i in range(10): totalCount += even[i] else: for i in range(10): totalCount += odd[i] return totalCount# Driver program to test above functionif __name__ == "__main__": keypad = [['1','2','3'], ['4','5','6'], ['7','8','9'], ['*','0','#']] print("Count for numbers of length ",1,": ", getCount(keypad, 1)) print("Count for numbers of length ",2,": ", getCount(keypad, 2)) print("Count for numbers of length ",3,": ", getCount(keypad, 3)) print("Count for numbers of length ",4,": ", getCount(keypad, 4)) print("Count for numbers of length ",5,": ", getCount(keypad, 5)) # This code is contributed by# ChitraNayal |
C#
// A Space Optimized C# program to // count number of possible numbers // of given lengthusing System; class GFG {// Return count of all possible numbers of // length n in a given numeric keyboardstatic int getCount(char [,]keypad, int n){ if(keypad == null || n <= 0) return 0; if(n == 1) return 10; // odd[i], even[i] arrays represent count of // numbers starting with digit i for any length j int []odd = new int[10]; int []even = new int[10]; int i = 0, j = 0, useOdd = 0, totalCount = 0; for (i = 0; i <= 9; i++) odd[i] = 1; // for j = 1 // Bottom Up calculation from j = 2 to n for (j = 2; j <= n; j++) { useOdd = 1 - useOdd; // Here we are explicitly writing lines // for each number 0 to 9. But it can always be // written as DFS on 4X3 grid using row, // column array valid moves if(useOdd == 1) { even[0] = odd[0] + odd[8]; even[1] = odd[1] + odd[2] + odd[4]; even[2] = odd[2] + odd[1] + odd[3] + odd[5]; even[3] = odd[3] + odd[2] + odd[6]; even[4] = odd[4] + odd[1] + odd[5] + odd[7]; even[5] = odd[5] + odd[2] + odd[4] + odd[8] + odd[6]; even[6] = odd[6] + odd[3] + odd[5] + odd[9]; even[7] = odd[7] + odd[4] + odd[8]; even[8] = odd[8] + odd[0] + odd[5] + odd[7] + odd[9]; even[9] = odd[9] + odd[6] + odd[8]; } else { odd[0] = even[0] + even[8]; odd[1] = even[1] + even[2] + even[4]; odd[2] = even[2] + even[1] + even[3] + even[5]; odd[3] = even[3] + even[2] + even[6]; odd[4] = even[4] + even[1] + even[5] + even[7]; odd[5] = even[5] + even[2] + even[4] + even[8] + even[6]; odd[6] = even[6] + even[3] + even[5] + even[9]; odd[7] = even[7] + even[4] + even[8]; odd[8] = even[8] + even[0] + even[5] + even[7] + even[9]; odd[9] = even[9] + even[6] + even[8]; } } // Get count of all possible numbers of // length "n" starting with digit 0, 1, 2, ..., 9 totalCount = 0; if(useOdd == 1) { for (i = 0; i <= 9; i++) totalCount += even[i]; } else { for (i = 0; i <= 9; i++) totalCount += odd[i]; } return totalCount;}// Driver Codepublic static void Main(String[] args) { char [,]keypad = {{'1','2','3'}, {'4','5','6'}, {'7','8','9'}, {'*','0','#'}}; Console.Write("Count for numbers of length {0}: {1}\n", 1, getCount(keypad, 1)); Console.Write("Count for numbers of length {0}: {1}\n", 2, getCount(keypad, 2)); Console.Write("Count for numbers of length {0}: {1}\n", 3, getCount(keypad, 3)); Console.Write("Count for numbers of length {0}: {1}\n", 4, getCount(keypad, 4)); Console.Write("Count for numbers of length {0}: {1}\n", 5, getCount(keypad, 5));}}// This code is contributed by 29AjayKumar |
Javascript
<script>// A Space Optimized javascript program to // count number of possible numbers // of given length// Return count of all possible numbers of // length n in a given numeric keyboardfunction getCount(keypad , n){ if(keypad == null || n <= 0) return 0; if(n == 1) return 10; // odd[i], even[i] arrays represent count of // numbers starting with digit i for any length j var odd = Array.from({length: 10}, (_, i) => 0); var even = Array.from({length: 10}, (_, i) => 0); var i = 0, j = 0, useOdd = 0, totalCount = 0; for (i = 0; i <= 9; i++) odd[i] = 1; // for j = 1 // Bottom Up calculation from j = 2 to n for (j = 2; j <= n; j++) { useOdd = 1 - useOdd; // Here we are explicitly writing lines // for each number 0 to 9. But it can always be // written as DFS on 4X3 grid using row, // column array valid moves if(useOdd == 1) { even[0] = odd[0] + odd[8]; even[1] = odd[1] + odd[2] + odd[4]; even[2] = odd[2] + odd[1] + odd[3] + odd[5]; even[3] = odd[3] + odd[2] + odd[6]; even[4] = odd[4] + odd[1] + odd[5] + odd[7]; even[5] = odd[5] + odd[2] + odd[4] + odd[8] + odd[6]; even[6] = odd[6] + odd[3] + odd[5] + odd[9]; even[7] = odd[7] + odd[4] + odd[8]; even[8] = odd[8] + odd[0] + odd[5] + odd[7] + odd[9]; even[9] = odd[9] + odd[6] + odd[8]; } else { odd[0] = even[0] + even[8]; odd[1] = even[1] + even[2] + even[4]; odd[2] = even[2] + even[1] + even[3] + even[5]; odd[3] = even[3] + even[2] + even[6]; odd[4] = even[4] + even[1] + even[5] + even[7]; odd[5] = even[5] + even[2] + even[4] + even[8] + even[6]; odd[6] = even[6] + even[3] + even[5] + even[9]; odd[7] = even[7] + even[4] + even[8]; odd[8] = even[8] + even[0] + even[5] + even[7] + even[9]; odd[9] = even[9] + even[6] + even[8]; } } // Get count of all possible numbers of // length "n" starting with digit 0, 1, 2, ..., 9 totalCount = 0; if(useOdd == 1) { for (i = 0; i <= 9; i++) totalCount += even[i]; } else { for (i = 0; i <= 9; i++) totalCount += odd[i]; } return totalCount;}// Driver Codevar keypad = [['1','2','3'], ['4','5','6'], ['7','8','9'], ['*','0','#']]; document.write("Count for numbers of length "+ 1+": "+ getCount(keypad, 1));document.write("<br>Count for numbers of length "+ 2+": "+ getCount(keypad, 2));document.write("<br>Count for numbers of length "+ 3+": "+ getCount(keypad, 3));document.write("<br>Count for numbers of length "+ 4+": "+ getCount(keypad, 4));document.write("<br>Count for numbers of length "+ 5+": "+ getCount(keypad, 5));// This code is contributed by 29AjayKumar </script> |
Output
Count for numbers of length 1: 10 Count for numbers of length 2: 36 Count for numbers of length 3: 138 Count for numbers of length 4: 532 Count for numbers of length 5: 2062
Time complexity :- O(N)
Auxiliary Space: O(1)
BRUTE APPROACH USING TABULATION:
Intuition:
- We declare a 2-D matrix of size arr[n+1][10]
- We put the no of times the keypad is pressed ie N in the row side and the numbers form 0-9 in the column side
- since it mentioned that we can press only left ,right down,up and the number itself after clicking
- so we store that numbers in 2-D array to keep a track of all number neighboring them
- Atlast we return the sum of the last row as that would given all the required possibilities.
Implementation:
C++
#include <bits/stdc++.h>using namespace std;long getCount(int N){ long dp[N + 1][10]; vector<vector<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 { dp[i][j] = 0; for (int k = 0; k < data[j].size(); k++) dp[i][j] += dp[i - 1][data[j][k]]; } } } long sum = 0; for (int j = 0; j <= 9; j++) { sum += dp[N][j]; } return sum;}int main(){ cout << getCount(5) << endl; return 0;} |
Java
// A Java program to count number of possible numbers of given lengthimport java.util.*;import java.io.*;class GFG { public static long getCount(int N) { // Your code goes here long dp[][] = new long[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]; } } } long sum = 0; for (int j = 0; j <= 9; j++) { sum += dp[N][j]; } return sum; } public static void main(String[] args) { System.out.println(getCount(5)); }}// This code is contributed by Rauank Singh |
Python3
# A Python3 program to count number of possible numbers of # given lengthdef get_count(N): dp = [[0] * 10 for _ in range(N + 1)] 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 i in range(1, N + 1): for j in range(10): if i == 1: dp[i][j] = 1 else: for prev in data[j]: dp[i][j] += dp[i - 1][prev] sum = 0 for j in range(10): sum += dp[N][j] return sumdef main(): print(get_count(5))if __name__ == '__main__': main() |
C#
using System;class GFG { public static long GetCount(int N) { // dp[i, j] represents the number of possible // numbers of length i ending with digit j (i.e., // the last digit is j). long[, ] dp = new long[N + 1, 10]; // The transitions from each digit to the next // possible digits. int[][] data = { new int[] { 0, 8 }, // Digits that can follow 0 new int[] { 1, 2, 4 }, // Digits that can follow 1 new int[] { 1, 2, 3, 5 }, // Digits that can follow 2 new int[] { 2, 3, 6 }, // Digits that can follow 3 new int[] { 1, 4, 5, 7 }, // Digits that can follow 4 new int[] { 2, 4, 5, 6, 8 }, // Digits that can follow 5 new int[] { 3, 5, 6, 9 }, // Digits that can follow 6 new int[] { 4, 7, 8 }, // Digits that can follow 7 new int[] { 5, 7, 8, 9, 0 }, // Digits that can follow 8 new int[] { 6, 8, 9 } // Digits that can follow 9 }; // Base case: For a single-digit number, there is // only one possible number ending with each digit. for (int j = 0; j <= 9; j++) dp[1, j] = 1; // Calculate the possible numbers for lengths from 2 // to N. for (int i = 2; i <= N; i++) { for (int j = 0; j <= 9; j++) { foreach(int prev in data[j]) { // The number of possible numbers of // length i ending with digit j is the // sum of the possible numbers of length // i-1 ending with each digit in // data[j]. dp[i, j] += dp[i - 1, prev]; } } } // Calculate the total count of possible numbers of // length N long sum = 0; for (int j = 0; j <= 9; j++) { sum += dp[N, j]; } return sum; } public static void Main(string[] args) { // Get the count of possible numbers of length 5 and // print the result. Console.WriteLine(GetCount(5)); }} |
Javascript
function getCount(N) { let dp = new Array(N + 1); for (let i = 0; i <= N; i++) { dp[i] = new Array(10).fill(0); } let 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 (let i = 1; i <= N; i++) { for (let j = 0; j < 10; j++) { if (i === 1) { dp[i][j] = 1; } else { for (let prev of data[j]) { dp[i][j] += dp[i - 1][prev]; } } } } let sum = 0; for (let j = 0; j < 10; j++) { sum += dp[N][j]; } return sum;}function main() { console.log(getCount(5));}main(); |
Output
2062
Time complexity :- O(N)
Space Complexity: O(N*10)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
