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
#include <bits/stdc++.h> NEW_LINE using namespace std ; string s ; int dp [ 1024 ] [ 10 ] [ 2 ] [ 2 ] ; int calcCnt ( int mask , int len , int smaller , int started ) { if ( len == s . size ( ) ) { return ( mask == 0 && started ) ; } if ( dp [ mask ] [ len ] [ smaller ] [ started ] != -1 ) return dp [ mask ] [ len ] [ smaller ] [ started ] ; int mx = 9 ; if ( ! smaller ) { mx = s [ len ] - '0' ; } int ans = 0 ; if ( started ) { for ( int i = 0 ; i <= mx ; i ++ ) { ans += calcCnt ( mask ^ ( 1 << i ) , len + 1 , smaller || ( i < s [ len ] - '0' ) , 1 ) ; } } else { ans = calcCnt ( mask , len + 1 , 1 , 0 ) ; for ( int i = 1 ; i <= mx ; i ++ ) { ans += calcCnt ( mask ^ ( 1 << i ) , len + 1 , smaller || ( i < s [ len ] - '0' ) , 1 ) ; } } return dp [ mask ] [ len ] [ smaller ] [ started ] = ans ; } int countInt ( int x ) { memset ( dp , -1 , sizeof ( dp ) ) ; s = to_string ( x ) ; return calcCnt ( 0 , 0 , 0 , 0 ) ; } int countIntInRange ( int L , int R ) { return countInt ( R ) - countInt ( L - 1 ) ; } int main ( ) { int L = 32 , R = 1010 ; cout << countIntInRange ( L , R ) ; return 0 ; }