Count of integers in range [ L , R ] having even frequency of each digit | Java 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
import java . util . * ; class GFG { static String s ; static int [ ] [ ] [ ] [ ] dp = new int [ 1024 ] [ 10 ] [ 2 ] [ 2 ] ; static boolean toBoolean ( int smaller ) { if ( smaller >= 1 ) return true ; else return false ; } static int calcCnt ( int mask , int len , int smaller , int started ) { + X3D3F3 : W3F3 : Y3F3 : X3 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 . charAt ( len ) - 48 ; } int ans = 0 ; if ( started != 0 ) { for ( int i = 0 ; i <= mx ; i ++ ) { ans += calcCnt ( mask ^ ( 1 << i ) , len + 1 , toBoolean ( smaller ) || ( i < ( int ) s . charAt ( 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 , toBoolean ( smaller ) || ( i < ( int ) s . charAt ( 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 = Integer . toString ( x ) ; return calcCnt ( 0 , 0 , 0 , 0 ) ; } static int countIntInRange ( int L , int R ) { return countInt ( R ) - countInt ( L - 1 ) ; } public static void main ( String [ ] args ) { int L = 32 , R = 1010 ; System . out . println ( countIntInRange ( L , R ) ) ; } }