Mobile Numeric Keypad Problem | Return count of all possible numbers of length n in a given numeric keyboard ; left , up , right , down move from current location ; taking n + 1 for simplicity - count [ i ] [ j ] will store number count starting with digit i and length j count [ 10 ] [ n + 1 ] ; count numbers starting with digit i and of lengths 0 and 1 ; Bottom up - Get number count of length 2 , 3 , 4 , ... , n ; Loop on keypad row ; Loop on keypad column ; Process for 0 to 9 digits ; Here we are counting the numbers starting with digit keypad [ i ] [ j ] and of length k keypad [ i ] [ j ] will become 1 st digit , and we need to look for ( k - 1 ) more digits ; 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 ; Get count of all possible numbers of length " n " starting with digit 0 , 1 , 2 , ... , 9 ; Driver code
def getCount ( keypad , n ) : NEW_LINE INDENT if ( keypad == None or n <= 0 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( n == 1 ) : NEW_LINE INDENT return 10 NEW_LINE DEDENT row = [ 0 , 0 , - 1 , 0 , 1 ] NEW_LINE col = [ 0 , - 1 , 0 , 1 , 0 ] NEW_LINE count = [ [ 0 ] * ( n + 1 ) ] * 10 NEW_LINE i = 0 NEW_LINE j = 0 NEW_LINE k = 0 NEW_LINE move = 0 NEW_LINE ro = 0 NEW_LINE co = 0 NEW_LINE num = 0 NEW_LINE nextNum = 0 NEW_LINE totalCount = 0 NEW_LINE for i in range ( 10 ) : NEW_LINE INDENT count [ i ] [ 0 ] = 0 NEW_LINE count [ i ] [ 1 ] = 1 NEW_LINE DEDENT for k in range ( 2 , n + 1 ) : NEW_LINE INDENT for i in range ( 4 ) : NEW_LINE INDENT for j in range ( 3 ) : NEW_LINE INDENT if ( keypad [ i ] [ j ] != ' * ' and keypad [ i ] [ j ] != ' # ' ) : NEW_LINE INDENT num = ord ( keypad [ i ] [ j ] ) - 48 NEW_LINE count [ num ] [ k ] = 0 NEW_LINE for move in range ( 5 ) : NEW_LINE INDENT ro = i + row [ move ] NEW_LINE co = j + col [ move ] NEW_LINE if ( ro >= 0 and ro <= 3 and co >= 0 and co <= 2 and keypad [ ro ] [ co ] != ' * ' and keypad [ ro ] [ co ] != ' # ' ) : NEW_LINE INDENT nextNum = ord ( keypad [ ro ] [ co ] ) - 48 NEW_LINE count [ num ] [ k ] += count [ nextNum ] [ k - 1 ] NEW_LINE DEDENT DEDENT DEDENT DEDENT DEDENT DEDENT totalCount = 0 NEW_LINE for i in range ( 10 ) : NEW_LINE INDENT totalCount += count [ i ] [ n ] NEW_LINE DEDENT return totalCount NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT keypad = [ [ '1' , '2' , '3' ] , [ '4' , '5' , '6' ] , [ '7' , '8' , '9' ] , [ ' * ' , '0' , ' # ' ] ] NEW_LINE print ( " Count ▁ for ▁ numbers ▁ of ▁ length " , 1 , " : " , getCount ( keypad , 1 ) ) NEW_LINE print ( " Count ▁ for ▁ numbers ▁ of ▁ length " , 2 , " : " , getCount ( keypad , 2 ) ) NEW_LINE print ( " Count ▁ for ▁ numbers ▁ of ▁ length " , 3 , " : " , getCount ( keypad , 3 ) ) NEW_LINE print ( " Count ▁ for ▁ numbers ▁ of ▁ length " , 4 , " : " , getCount ( keypad , 4 ) ) NEW_LINE print ( " Count ▁ for ▁ numbers ▁ of ▁ length " , 5 , " : " , getCount ( keypad , 5 ) ) NEW_LINE DEDENT