Count of integers in range [ L , R ] having even frequency of each digit | C # program for the above approach ; 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
using System ; using System . Collections . Generic ; class GFG { static string s ; static int [ , , , ] dp = new int [ 1024 , 10 , 2 , 2 ] ; static int calcCnt ( int mask , int len , int smaller , int started ) { if ( len == s . Length ) { if ( mask == 0 && started != 0 ) return 1 ; else return 0 ; } if ( dp [ mask , len , smaller , started ] != - 1 ) return dp [ mask , len , smaller , started ] ; int mx = 9 ; if ( smaller == 0 ) { mx = ( int ) s [ len ] - 48 ; } int ans = 0 ; if ( started != 0 ) { for ( int i = 0 ; i <= mx ; i ++ ) { ans += calcCnt ( mask ^ ( 1 << i ) , len + 1 , Convert . ToBoolean ( smaller ) || ( i < ( int ) s [ len ] - 48 ) ? 1 : 0 , 1 ) ; } } else { ans = calcCnt ( mask , len + 1 , 1 , 0 ) ; for ( int i = 1 ; i <= mx ; i ++ ) { ans += calcCnt ( mask ^ ( 1 << i ) , len + 1 , Convert . ToBoolean ( smaller ) || ( i < ( int ) s [ len ] - 48 ) ? 1 : 0 , 1 ) ; } } dp [ mask , len , smaller , started ] = ans ; return ans ; } static int countInt ( int x ) { for ( int i = 0 ; i < 1024 ; i ++ ) { for ( int j = 0 ; j < 10 ; j ++ ) { for ( int k = 0 ; k < 2 ; k ++ ) { for ( int l = 0 ; l < 2 ; l ++ ) dp [ i , j , k , l ] = - 1 ; } } } s = x . ToString ( ) ; return calcCnt ( 0 , 0 , 0 , 0 ) ; } static int countIntInRange ( int L , int R ) { return countInt ( R ) - countInt ( L - 1 ) ; } public static void Main ( ) { int L = 32 , R = 1010 ; Console . Write ( countIntInRange ( L , R ) ) ; } }