Count of N | Python program for the above approach ; Function to find the number of N digit numbers such that at least one digit occurs more than once ; Base Case ; If repeated is true , then for remaining positions any digit can be placed ; If the current state has already been computed , then return it ; Stores the count of number for the current recursive calls ; If n = 1 , 0 can be also placed ; If a digit has occurred for the second time , then set repeated to 1 ; Otherwise ; For remaining positions any digit can be placed ; If a digit has occurred for the second time , then set repeated to 1 ; Return the resultant count for the current recursive call ; Function to count all the N - digit numbers having at least one digit 's occurrence more than once ; Function to count all possible number satisfying the given criteria ; Driver Code
dp = [ [ [ - 1 for i in range ( 2 ) ] for i in range ( 1 << 10 ) ] for i in range ( 50 ) ] NEW_LINE def countOfNumbers ( digit , mask , repeated , n ) : NEW_LINE INDENT global dp NEW_LINE if ( digit == n + 1 ) : NEW_LINE INDENT if ( repeated == True ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT return 0 NEW_LINE DEDENT if ( repeated == True ) : NEW_LINE INDENT return pow ( 10 , n - digit + 1 ) NEW_LINE DEDENT val = dp [ digit ] [ mask ] [ repeated ] NEW_LINE if ( val != - 1 ) : NEW_LINE INDENT return val NEW_LINE DEDENT val = 4 NEW_LINE if ( digit == 1 ) : NEW_LINE INDENT for i in range ( ( 0 if ( n == 1 ) else 1 ) , 10 ) : NEW_LINE INDENT if ( mask & ( 1 << i ) ) : NEW_LINE INDENT val += countOfNumbers ( digit + 1 , mask | ( 1 << i ) , 1 , n ) NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT val += countOfNumbers ( digit + 1 , mask | ( 1 << i ) , 0 , n ) NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT for i in range ( 10 ) : NEW_LINE INDENT if ( mask & ( 1 << i ) ) : NEW_LINE INDENT val += countOfNumbers ( digit + 1 , mask | ( 1 << i ) , 1 , n ) NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT val += countOfNumbers ( digit + 1 , mask | ( 1 << i ) , 0 , n ) NEW_LINE DEDENT DEDENT dp [ digit ] [ mask ] [ repeated ] = val NEW_LINE return dp [ digit ] [ mask ] [ repeated ] NEW_LINE DEDENT def countNDigitNumber ( N ) : NEW_LINE INDENT print ( countOfNumbers ( 1 , 0 , 0 , N ) ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 2 NEW_LINE countNDigitNumber ( N ) NEW_LINE DEDENT