Count of integers in range [ L , R ] having even frequency of each digit | Stores the upper limit of the range ; Stores the overlapping states ; Recursive Function to calculate the count of valid integers in the range [ 1 , s ] using memoization ; Base Case ; If current integer has even count of digits and is not repeated ; If current state is already considered ; Stores the maximum valid digit at the current index ; Stores the count of valid integers ; If the current digit is not the most significant digit , i . e , the integer is already started ; Iterate through all valid digits ; Recursive call for ith digit at the current index ; Recursive call for integers having leading zeroes in the beginning ; Iterate through all valid digits as most significant digits ; Recursive call for ith digit at the current index ; Return answer ; Function to calculate valid number in the range [ 1 , X ] ; Initialize dp array with - 1 ; Store the range in form of string ; Return Count ; Function to find the count of integers in the range [ L , R ] such that the frequency of each digit is even ; Driver Code
s = " " NEW_LINE dp = [ [ [ [ 0 for _ in range ( 2 ) ] for _ in range ( 2 ) ] for _ in range ( 10 ) ] for _ in range ( 1024 ) ] NEW_LINE def calcCnt ( mask , sz , smaller , started ) : NEW_LINE INDENT if ( sz == len ( s ) ) : NEW_LINE INDENT return ( mask == 0 and started ) NEW_LINE DEDENT if ( dp [ mask ] [ sz ] [ smaller ] [ started ] != - 1 ) : NEW_LINE INDENT return dp [ mask ] [ sz ] [ smaller ] [ started ] NEW_LINE DEDENT mx = 9 NEW_LINE if ( not smaller ) : NEW_LINE INDENT mx = ord ( s [ sz ] ) - ord ( '0' ) NEW_LINE DEDENT ans = 0 NEW_LINE if ( started ) : NEW_LINE INDENT for i in range ( 0 , mx + 1 ) : NEW_LINE INDENT ans += calcCnt ( mask ^ ( 1 << i ) , sz + 1 , smaller or ( i < ord ( s [ sz ] ) - ord ( '0' ) ) , 1 ) NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT ans = calcCnt ( mask , sz + 1 , 1 , 0 ) NEW_LINE for i in range ( 1 , mx + 1 ) : NEW_LINE INDENT ans += calcCnt ( mask ^ ( 1 << i ) , sz + 1 , smaller or ( i < ord ( s [ sz ] ) - ord ( '0' ) ) , 1 ) NEW_LINE DEDENT DEDENT dp [ mask ] [ sz ] [ smaller ] [ started ] = ans NEW_LINE return dp [ mask ] [ sz ] [ smaller ] [ started ] NEW_LINE DEDENT def countInt ( x ) : NEW_LINE INDENT global dp NEW_LINE dp = [ [ [ [ - 1 for _ in range ( 2 ) ] for _ in range ( 2 ) ] for _ in range ( 10 ) ] for _ in range ( 1024 ) ] NEW_LINE global s NEW_LINE s = str ( x ) NEW_LINE return calcCnt ( 0 , 0 , 0 , 0 ) NEW_LINE DEDENT def countIntInRange ( L , R ) : NEW_LINE INDENT return countInt ( R ) - countInt ( L - 1 ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT L = 32 NEW_LINE R = 1010 NEW_LINE print ( countIntInRange ( L , R ) ) NEW_LINE DEDENT