{"id":27207,"date":"2018-01-03T22:21:45","date_gmt":"2018-01-03T16:51:45","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27207"},"modified":"2018-01-03T22:21:45","modified_gmt":"2018-01-03T16:51:45","slug":"mobile-numeric-keypad-problem","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/mobile-numeric-keypad-problem\/","title":{"rendered":"Mobile Numeric Keypad Problem"},"content":{"rendered":"

\"Mobile<\/p>\n

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 # ).<\/span>
\nGiven a number N, find out the number of possible numbers of given length.<\/p>\n

Examples:
\nFor N=1, number of possible numbers would be 10 (0, 1, 2, 3, \u2026., 9)
\nFor N=2, number of possible numbers would be 36
\nPossible numbers: 00,08 11,12,14 22,21,23,25 and so on.
\nIf we start with 0, valid numbers will be 00, 08 (count: 2)
\nIf we start with 1, valid numbers will be 11, 12, 14 (count: 3)
\nIf we start with 2, valid numbers will be 22, 21, 23,25 (count: 4)
\nIf we start with 3, valid numbers will be 33, 32, 36 (count: 3)
\nIf we start with 4, valid numbers will be 44,41,45,47 (count: 4)
\nIf we start with 5, valid numbers will be 55,54,52,56,58 (count: 5)
\n\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026
\n\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026<\/p>\n

We need to print the count of possible numbers.<\/p>\n[ad type=\u201dbanner\u201d]\n

We strongly recommend to minimize the browser and try this yourself first.<\/strong><\/p>\n

N = 1 is trivial case, number of possible numbers would be 10 (0, 1, 2, 3, \u2026., 9)
\nFor 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).<\/p>\n

Recursive Solution:<\/strong>
\nMobile Keypad is a rectangular grid of 4X3 (4 rows and 3 columns)
\nLets say Count(i, j, N) represents the count of N length numbers starting from position (i, j)<\/p>\n

If N = 1\r\n  Count(i, j, N) = 10  \r\nElse\r\n  Count(i, j, N) = Sum of all Count(r, c, N-1) where (r, c) is new \r\n                   position after valid move of length 1 from current \r\n                   position (i, j)<\/pre>\n
Following is C implementation of above recursive formula.<\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%2F%2F%20A%20Naive%20Recursive%20C%20program%20to%20count%20number%20of%20possible%20numbers%0A%2F%2F%20of%20given%20length%0A%23include%20%3Cstdio.h%3E%0A%20%0A%2F%2F%20left%2C%20up%2C%20right%2C%20down%20move%20from%20current%20location%0Aint%20row%5B%5D%20%3D%20%7B0%2C%200%2C%20-1%2C%200%2C%201%7D%3B%0Aint%20col%5B%5D%20%3D%20%7B0%2C%20-1%2C%200%2C%201%2C%200%7D%3B%0A%20%0A%2F%2F%20Returns%20count%20of%20numbers%20of%20length%20n%20starting%20from%20key%20position%0A%2F%2F%20(i%2C%20j)%20in%20a%20numeric%20keyboard.%0Aint%20getCountUtil(char%20keypad%5B%5D%5B3%5D%2C%20int%20i%2C%20int%20j%2C%20int%20n)%0A%7B%0A%20%20%20%20if%20(keypad%20%3D%3D%20NULL%20%7C%7C%20n%20%3C%3D%200)%0A%20%20%20%20%20%20%20%20return%200%3B%0A%20%0A%20%20%20%20%2F%2F%20From%20a%20given%20key%2C%20only%20one%20number%20is%20possible%20of%20length%201%0A%20%20%20%20if%20(n%20%3D%3D%201)%0A%20%20%20%20%20%20%20%20return%201%3B%0A%20%0A%20%20%20%20int%20k%3D0%2C%20move%3D0%2C%20ro%3D0%2C%20co%3D0%2C%20totalCount%20%3D%200%3B%0A%20%0A%20%20%20%20%2F%2F%20move%20left%2C%20up%2C%20right%2C%20down%20from%20current%20location%20and%20if%0A%20%20%20%20%2F%2F%20new%20location%20is%20valid%2C%20then%20get%20number%20count%20of%20length%0A%20%20%20%20%2F%2F%20(n-1)%20from%20that%20new%20position%20and%20add%20in%20count%20obtained%20so%20far%0A%20%20%20%20for%20(move%3D0%3B%20move%3C5%3B%20move%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20ro%20%3D%20i%20%2B%20row%5Bmove%5D%3B%0A%20%20%20%20%20%20%20%20co%20%3D%20j%20%2B%20col%5Bmove%5D%3B%0A%20%20%20%20%20%20%20%20if%20(ro%20%3E%3D%200%20%26%26%20ro%20%3C%3D%203%20%26%26%20co%20%3E%3D0%20%26%26%20co%20%3C%3D%202%20%26%26%0A%20%20%20%20%20%20%20%20%20%20%20keypad%5Bro%5D%5Bco%5D%20!%3D%20\u2019*\u2019%20%26%26%20keypad%5Bro%5D%5Bco%5D%20!%3D%20\u2019%23\u2032)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20totalCount%20%2B%3D%20getCountUtil(keypad%2C%20ro%2C%20co%2C%20n-1)%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20return%20totalCount%3B%0A%7D%0A%20%0A%2F%2F%20Return%20count%20of%20all%20possible%20numbers%20of%20length%20n%0A%2F%2F%20in%20a%20given%20numeric%20keyboard%0Aint%20getCount(char%20keypad%5B%5D%5B3%5D%2C%20int%20n)%0A%7B%0A%20%20%20%20%2F%2F%20Base%20cases%0A%20%20%20%20if%20(keypad%20%3D%3D%20NULL%20%7C%7C%20n%20%3C%3D%200)%0A%20%20%20%20%20%20%20%20return%200%3B%0A%20%20%20%20if%20(n%20%3D%3D%201)%0A%20%20%20%20%20%20%20%20return%2010%3B%0A%20%0A%20%20%20%20int%20i%3D0%2C%20j%3D0%2C%20totalCount%20%3D%200%3B%0A%20%20%20%20for%20(i%3D0%3B%20i%3C4%3B%20i%2B%2B)%20%20%2F%2F%20Loop%20on%20keypad%20row%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20for%20(j%3D0%3B%20j%3C3%3B%20j%2B%2B)%20%20%20%2F%2F%20Loop%20on%20keypad%20column%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Process%20for%200%20to%209%20digits%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(keypad%5Bi%5D%5Bj%5D%20!%3D%20\u2019*\u2019%20%26%26%20keypad%5Bi%5D%5Bj%5D%20!%3D%20\u2019%23\u2032)%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Get%20count%20when%20number%20is%20starting%20from%20key%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20position%20(i%2C%20j)%20and%20add%20in%20count%20obtained%20so%20far%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20totalCount%20%2B%3D%20getCountUtil(keypad%2C%20i%2C%20j%2C%20n)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%20%20%20return%20totalCount%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20function%0Aint%20main(int%20argc%2C%20char%20*argv%5B%5D)%0A%7B%0A%20%20%20char%20keypad%5B4%5D%5B3%5D%20%3D%20%7B%7B\u20191\u2019%2C\u20192\u2019%2C\u20193\u2019%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B\u20194\u2019%2C\u20195\u2019%2C\u20196\u2019%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B\u20197\u2019%2C\u20198\u2019%2C\u20199\u2019%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B\u2019*\u2019%2C\u20190\u2019%2C\u2019%23\u2019%7D%7D%3B%0A%20%20%20printf(%22Count%20for%20numbers%20of%20length%20%25d%3A%20%25d%5Cn%22%2C%201%2C%20getCount(keypad%2C%201))%3B%0A%20%20%20printf(%22Count%20for%20numbers%20of%20length%20%25d%3A%20%25d%5Cn%22%2C%202%2C%20getCount(keypad%2C%202))%3B%0A%20%20%20printf(%22Count%20for%20numbers%20of%20length%20%25d%3A%20%25d%5Cn%22%2C%203%2C%20getCount(keypad%2C%203))%3B%0A%20%20%20printf(%22Count%20for%20numbers%20of%20length%20%25d%3A%20%25d%5Cn%22%2C%204%2C%20getCount(keypad%2C%204))%3B%0A%20%20%20printf(%22Count%20for%20numbers%20of%20length%20%25d%3A%20%25d%5Cn%22%2C%205%2C%20getCount(keypad%2C%205))%3B%0A%20%0A%20%20%20return%200%3B%0A%7D\u201d message=\u201dC\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n
Output:<\/p>\n
Count for numbers of length 1: 10\r\nCount for numbers of length 2: 36\r\nCount for numbers of length 3: 138\r\nCount for numbers of length 4: 532\r\nCount for numbers of length 5: 2062\r\n<\/pre>\n[ad type=\u201dbanner\u201d]\n
Dynamic Programming<\/strong>
\nThere 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 \u20184\u2019 and \u20188\u2019), we can see there are few repeated traversals for N = 2 (e.g. 4 -> 1, 6 -> 3, 8 -> 9, 8 -> 7 etc).<\/p>\n
\"Mobile<\/p>\n
\"Mobile<\/p>\n
Since the problem has both properties: Optimal Substructure and Overlapping Subproblems, it can be efficiently solved using dynamic programming.<\/p>\n[ad type=\u201dbanner\u201d]\n
Following is C program for dynamic programming implementation.<\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%2F%2F%20A%20Dynamic%20Programming%20based%20C%20program%20to%20count%20number%20of%0A%2F%2F%20possible%20numbers%20of%20given%20length%0A%23include%20%3Cstdio.h%3E%0A%20%0A%2F%2F%20Return%20count%20of%20all%20possible%20numbers%20of%20length%20n%0A%2F%2F%20in%20a%20given%20numeric%20keyboard%0Aint%20getCount(char%20keypad%5B%5D%5B3%5D%2C%20int%20n)%0A%7B%0A%20%20%20%20if(keypad%20%3D%3D%20NULL%20%7C%7C%20n%20%3C%3D%200)%0A%20%20%20%20%20%20%20%20return%200%3B%0A%20%20%20%20if(n%20%3D%3D%201)%0A%20%20%20%20%20%20%20%20return%2010%3B%0A%20%0A%20%20%20%20%2F%2F%20left%2C%20up%2C%20right%2C%20down%20move%20from%20current%20location%0A%20%20%20%20int%20row%5B%5D%20%3D%20%7B0%2C%200%2C%20-1%2C%200%2C%201%7D%3B%0A%20%20%20%20int%20col%5B%5D%20%3D%20%7B0%2C%20-1%2C%200%2C%201%2C%200%7D%3B%0A%20%0A%20%20%20%20%2F%2F%20taking%20n%2B1%20for%20simplicity%20-%20count%5Bi%5D%5Bj%5D%20will%20store%0A%20%20%20%20%2F%2F%20number%20count%20starting%20with%20digit%20i%20and%20length%20j%0A%20%20%20%20int%20count%5B10%5D%5Bn%2B1%5D%3B%0A%20%20%20%20int%20i%3D0%2C%20j%3D0%2C%20k%3D0%2C%20move%3D0%2C%20ro%3D0%2C%20co%3D0%2C%20num%20%3D%200%3B%0A%20%20%20%20int%20nextNum%3D0%2C%20totalCount%20%3D%200%3B%0A%20%0A%20%20%20%20%2F%2F%20count%20numbers%20starting%20with%20digit%20i%20and%20of%20lengths%200%20and%201%0A%20%20%20%20for%20(i%3D0%3B%20i%3C%3D9%3B%20i%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20count%5Bi%5D%5B0%5D%20%3D%200%3B%0A%20%20%20%20%20%20%20%20count%5Bi%5D%5B1%5D%20%3D%201%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Bottom%20up%20-%20Get%20number%20count%20of%20length%202%2C%203%2C%204%2C%20\u2026%20%2C%20n%0A%20%20%20%20for%20(k%3D2%3B%20k%3C%3Dn%3B%20k%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20for%20(i%3D0%3B%20i%3C4%3B%20i%2B%2B)%20%20%2F%2F%20Loop%20on%20keypad%20row%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20(j%3D0%3B%20j%3C3%3B%20j%2B%2B)%20%20%20%2F%2F%20Loop%20on%20keypad%20column%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Process%20for%200%20to%209%20digits%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20(keypad%5Bi%5D%5Bj%5D%20!%3D%20\u2019*\u2019%20%26%26%20keypad%5Bi%5D%5Bj%5D%20!%3D%20\u2019%23\u2032)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Here%20we%20are%20counting%20the%20numbers%20starting%20with%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20digit%20keypad%5Bi%5D%5Bj%5D%20and%20of%20length%20k%20keypad%5Bi%5D%5Bj%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20will%20become%201st%20digit%2C%20and%20we%20need%20to%20look%20for%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20(k-1)%20more%20digits%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20num%20%3D%20keypad%5Bi%5D%5Bj%5D%20-%20\u20190\u2019%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20count%5Bnum%5D%5Bk%5D%20%3D%200%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20move%20left%2C%20up%2C%20right%2C%20down%20from%20current%20location%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20and%20if%20new%20location%20is%20valid%2C%20then%20get%20number%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20count%20of%20length%20(k-1)%20from%20that%20new%20digit%20and%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20add%20in%20count%20we%20found%20so%20far%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20(move%3D0%3B%20move%3C5%3B%20move%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20ro%20%3D%20i%20%2B%20row%5Bmove%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20co%20%3D%20j%20%2B%20col%5Bmove%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20(ro%20%3E%3D%200%20%26%26%20ro%20%3C%3D%203%20%26%26%20co%20%3E%3D0%20%26%26%20co%20%3C%3D%202%20%26%26%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20keypad%5Bro%5D%5Bco%5D%20!%3D%20\u2019*\u2019%20%26%26%20keypad%5Bro%5D%5Bco%5D%20!%3D%20\u2019%23\u2032)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20nextNum%20%3D%20keypad%5Bro%5D%5Bco%5D%20-%20\u20190\u2019%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20count%5Bnum%5D%5Bk%5D%20%2B%3D%20count%5BnextNum%5D%5Bk-1%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Get%20count%20of%20all%20possible%20numbers%20of%20length%20%22n%22%20starting%0A%20%20%20%20%2F%2F%20with%20digit%200%2C%201%2C%202%2C%20\u2026%2C%209%0A%20%20%20%20totalCount%20%3D%200%3B%0A%20%20%20%20for%20(i%3D0%3B%20i%3C%3D9%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20totalCount%20%2B%3D%20count%5Bi%5D%5Bn%5D%3B%0A%20%20%20%20return%20totalCount%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20function%0Aint%20main(int%20argc%2C%20char%20*argv%5B%5D)%0A%7B%0A%20%20%20char%20keypad%5B4%5D%5B3%5D%20%3D%20%7B%7B\u20191\u2019%2C\u20192\u2019%2C\u20193\u2019%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B\u20194\u2019%2C\u20195\u2019%2C\u20196\u2019%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B\u20197\u2019%2C\u20198\u2019%2C\u20199\u2019%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B\u2019*\u2019%2C\u20190\u2019%2C\u2019%23\u2019%7D%7D%3B%0A%20%20%20printf(%22Count%20for%20numbers%20of%20length%20%25d%3A%20%25d%5Cn%22%2C%201%2C%20getCount(keypad%2C%201))%3B%0A%20%20%20printf(%22Count%20for%20numbers%20of%20length%20%25d%3A%20%25d%5Cn%22%2C%202%2C%20getCount(keypad%2C%202))%3B%0A%20%20%20printf(%22Count%20for%20numbers%20of%20length%20%25d%3A%20%25d%5Cn%22%2C%203%2C%20getCount(keypad%2C%203))%3B%0A%20%20%20printf(%22Count%20for%20numbers%20of%20length%20%25d%3A%20%25d%5Cn%22%2C%204%2C%20getCount(keypad%2C%204))%3B%0A%20%20%20printf(%22Count%20for%20numbers%20of%20length%20%25d%3A%20%25d%5Cn%22%2C%205%2C%20getCount(keypad%2C%205))%3B%0A%20%0A%20%20%20return%200%3B%0A%7D\u201d message=\u201dC\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n
Output:<\/p>\n
Count for numbers of length 1: 10\r\nCount for numbers of length 2: 36\r\nCount for numbers of length 3: 138\r\nCount for numbers of length 4: 532\r\nCount for numbers of length 5: 2062<\/pre>\n[ad type=\u201dbanner\u201d]\n
A Space Optimized Solution:<\/strong>
\nThe 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.<\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%2F%2F%20A%20Space%20Optimized%20C%20program%20to%20count%20number%20of%20possible%20numbers%0A%2F%2F%20of%20given%20length%0A%23include%20%3Cstdio.h%3E%0A%20%0A%2F%2F%20Return%20count%20of%20all%20possible%20numbers%20of%20length%20n%0A%2F%2F%20in%20a%20given%20numeric%20keyboard%0Aint%20getCount(char%20keypad%5B%5D%5B3%5D%2C%20int%20n)%0A%7B%0A%20%20%20%20if(keypad%20%3D%3D%20NULL%20%7C%7C%20n%20%3C%3D%200)%0A%20%20%20%20%20%20%20%20return%200%3B%0A%20%20%20%20if(n%20%3D%3D%201)%0A%20%20%20%20%20%20%20%20return%2010%3B%0A%20%0A%20%20%20%20%2F%2F%20odd%5Bi%5D%2C%20even%5Bi%5D%20arrays%20represent%20count%20of%20numbers%20starting%0A%20%20%20%20%2F%2F%20with%20digit%20i%20for%20any%20length%20j%0A%20%20%20%20int%20odd%5B10%5D%2C%20even%5B10%5D%3B%0A%20%20%20%20int%20i%20%3D%200%2C%20j%20%3D%200%2C%20useOdd%20%3D%200%2C%20totalCount%20%3D%200%3B%0A%20%0A%20%20%20%20for%20(i%3D0%3B%20i%3C%3D9%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20odd%5Bi%5D%20%3D%201%3B%20%20%2F%2F%20for%20j%20%3D%201%0A%20%0A%20%20%20%20for%20(j%3D2%3B%20j%3C%3Dn%3B%20j%2B%2B)%20%2F%2F%20Bottom%20Up%20calculation%20from%20j%20%3D%202%20to%20n%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20useOdd%20%3D%201%20-%20useOdd%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Here%20we%20are%20explicitly%20writing%20lines%20for%20each%20number%200%0A%20%20%20%20%20%20%20%20%2F%2F%20to%209.%20But%20it%20can%20always%20be%20written%20as%20DFS%20on%204X3%20grid%0A%20%20%20%20%20%20%20%20%2F%2F%20using%20row%2C%20column%20array%20valid%20moves%0A%20%20%20%20%20%20%20%20if(useOdd%20%3D%3D%201)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20even%5B0%5D%20%3D%20odd%5B0%5D%20%2B%20odd%5B8%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20even%5B1%5D%20%3D%20odd%5B1%5D%20%2B%20odd%5B2%5D%20%2B%20odd%5B4%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20even%5B2%5D%20%3D%20odd%5B2%5D%20%2B%20odd%5B1%5D%20%2B%20odd%5B3%5D%20%2B%20odd%5B5%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20even%5B3%5D%20%3D%20odd%5B3%5D%20%2B%20odd%5B2%5D%20%2B%20odd%5B6%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20even%5B4%5D%20%3D%20odd%5B4%5D%20%2B%20odd%5B1%5D%20%2B%20odd%5B5%5D%20%2B%20odd%5B7%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20even%5B5%5D%20%3D%20odd%5B5%5D%20%2B%20odd%5B2%5D%20%2B%20odd%5B4%5D%20%2B%20odd%5B8%5D%20%2B%20odd%5B6%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20even%5B6%5D%20%3D%20odd%5B6%5D%20%2B%20odd%5B3%5D%20%2B%20odd%5B5%5D%20%2B%20odd%5B9%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20even%5B7%5D%20%3D%20odd%5B7%5D%20%2B%20odd%5B4%5D%20%2B%20odd%5B8%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20even%5B8%5D%20%3D%20odd%5B8%5D%20%2B%20odd%5B0%5D%20%2B%20odd%5B5%5D%20%2B%20odd%5B7%5D%20%2B%20odd%5B9%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20even%5B9%5D%20%3D%20odd%5B9%5D%20%2B%20odd%5B6%5D%20%2B%20odd%5B8%5D%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20odd%5B0%5D%20%3D%20even%5B0%5D%20%2B%20even%5B8%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20odd%5B1%5D%20%3D%20even%5B1%5D%20%2B%20even%5B2%5D%20%2B%20even%5B4%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20odd%5B2%5D%20%3D%20even%5B2%5D%20%2B%20even%5B1%5D%20%2B%20even%5B3%5D%20%2B%20even%5B5%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20odd%5B3%5D%20%3D%20even%5B3%5D%20%2B%20even%5B2%5D%20%2B%20even%5B6%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20odd%5B4%5D%20%3D%20even%5B4%5D%20%2B%20even%5B1%5D%20%2B%20even%5B5%5D%20%2B%20even%5B7%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20odd%5B5%5D%20%3D%20even%5B5%5D%20%2B%20even%5B2%5D%20%2B%20even%5B4%5D%20%2B%20even%5B8%5D%20%2B%20even%5B6%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20odd%5B6%5D%20%3D%20even%5B6%5D%20%2B%20even%5B3%5D%20%2B%20even%5B5%5D%20%2B%20even%5B9%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20odd%5B7%5D%20%3D%20even%5B7%5D%20%2B%20even%5B4%5D%20%2B%20even%5B8%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20odd%5B8%5D%20%3D%20even%5B8%5D%20%2B%20even%5B0%5D%20%2B%20even%5B5%5D%20%2B%20even%5B7%5D%20%2B%20even%5B9%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20odd%5B9%5D%20%3D%20even%5B9%5D%20%2B%20even%5B6%5D%20%2B%20even%5B8%5D%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Get%20count%20of%20all%20possible%20numbers%20of%20length%20%22n%22%20starting%0A%20%20%20%20%2F%2F%20with%20digit%200%2C%201%2C%202%2C%20\u2026%2C%209%0A%20%20%20%20totalCount%20%3D%200%3B%0A%20%20%20%20if(useOdd%20%3D%3D%201)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20for%20(i%3D0%3B%20i%3C%3D9%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20totalCount%20%2B%3D%20even%5Bi%5D%3B%0A%20%20%20%20%7D%0A%20%20%20%20else%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20for%20(i%3D0%3B%20i%3C%3D9%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20totalCount%20%2B%3D%20odd%5Bi%5D%3B%0A%20%20%20%20%7D%0A%20%20%20%20return%20totalCount%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20function%0Aint%20main()%0A%7B%0A%20%20%20%20char%20keypad%5B4%5D%5B3%5D%20%3D%20%7B%7B\u20191\u2019%2C\u20192\u2019%2C\u20193\u2019%7D%2C%0A%20%20%20%20%20%20%20%20%7B\u20194\u2019%2C\u20195\u2019%2C\u20196\u2019%7D%2C%0A%20%20%20%20%20%20%20%20%7B\u20197\u2019%2C\u20198\u2019%2C\u20199\u2019%7D%2C%0A%20%20%20%20%20%20%20%20%7B\u2019*\u2019%2C\u20190\u2019%2C\u2019%23\u2019%7D%0A%20%20%20%20%7D%3B%0A%20%20%20%20printf(%22Count%20for%20numbers%20of%20length%20%25d%3A%20%25d%5Cn%22%2C%201%2C%20getCount(keypad%2C%201))%3B%0A%20%20%20%20printf(%22Count%20for%20numbers%20of%20length%20%25d%3A%20%25d%5Cn%22%2C%202%2C%20getCount(keypad%2C%202))%3B%0A%20%20%20%20printf(%22Count%20for%20numbers%20of%20length%20%25d%3A%20%25d%5Cn%22%2C%203%2C%20getCount(keypad%2C%203))%3B%0A%20%20%20%20printf(%22Count%20for%20numbers%20of%20length%20%25d%3A%20%25d%5Cn%22%2C%204%2C%20getCount(keypad%2C%204))%3B%0A%20%20%20%20printf(%22Count%20for%20numbers%20of%20length%20%25d%3A%20%25d%5Cn%22%2C%205%2C%20getCount(keypad%2C%205))%3B%0A%20%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201dC\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n
Output:<\/p>\n
Count for numbers of length 1: 10\r\nCount for numbers of length 2: 36\r\nCount for numbers of length 3: 138\r\nCount for numbers of length 4: 532\r\nCount for numbers of length 5: 2062<\/pre>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"
Mobile Numeric Keypad Problem – Dynamic Programming Given the mobile numeric keypad. You can only press buttons that are up, left, right or down <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,70145,83849],"tags":[61375,61366,72847,81075,72842,72845,70483,72848,81074,81076,81094,81098,81097,81091,72855,72853],"class_list":["post-27207","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-dynamic-programming","category-mobile-numeric-keypad-problem","tag-best-keypad-mobile","tag-best-keypad-phone","tag-concept-of-dynamic-programming","tag-count-of-possible-words-from-mobile-keypad","tag-define-dynamic-programming","tag-definition-of-dynamic-programming","tag-dynamic-programming","tag-dynamic-programming-code-generation-algorithm","tag-mobile-numeric-keypad-problem","tag-mobile-numeric-keypad-problem-solution-in-java","tag-mobile-phones-with-keypad","tag-mobile-with-keypad","tag-nokia-keypad-mobile","tag-nokia-keypad-phones","tag-simple-dynamic-programming-example","tag-types-of-dynamic-programming"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27207","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=27207"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27207\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27207"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27207"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27207"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}