Count of integers in range [L, R] having even frequency of each digit
Given two integers L and R, the task is to find the count of integers in the range [L, R] such that the frequency of each digit in the integer is even.
Examples:
Input: L = 47, R = 999
Output: 5
Explanation: The integers that are in range [47, 999] and follow the given condition are {55, 66, 77, 88, 99}.Input: L = 32, R = 1010
Output: 9
Explanation: The integers that are in range [32, 1010] and follow the given condition are {33, 44, 55, 66, 77, 88, 99, 1001, 1010}.
Approach: The above problem can be solved with the help of Bitmasking and Dynamic Programming. Below are some observations that can be used to solve the given problem:
- Bitmask having 10 bits can be used to store the parity of each digit in the range [0, 9] where an ith set bit will represent the frequency of digit i in the integer as odd.
- Let’s define a function countInt(X) to find the count of valid integers in the range [1, X]. Therefore, the answer for range [L, R] can be calculated as countInt(R) – countInt(L-1).
Consider a 4D array say dp[][][][], wherein dp[mask][length][smaller][started], where mask represents the Bitmask denoting the parity of each digit from 0 to 9, length represents the total count of digits in the current number, smaller represents whether the current number is smaller than the upper bound i.e, lies in the given range and started will keep track of repeating numbers due to the leading zeroes. Below are the steps to follow:
- Create a recursive function to iterate through each index of the integer and recursively call the function for each valid digit at the current index of the integer.
- Keep track of the leading zeroes in the variable started in order to prevent their repetition in the count.
- If the current index is the most significant index, the valid digits must be in the range [1, 9] otherwise they can be in the range [0, 9].
- The current digit is a valid digit if after putting the digit in the current index of the integer, formed integer <= Upper Bound of the range.
- Memorize the count for each state and return the memorized value if the current state is already calculated.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Stores the upper limit of the range string s; // Stores the overlapping states int dp[1024][10][2][2]; // Recursive Function to calculate the // count of valid integers in the range // [1, s] using memoization int calcCnt( int mask, int len, int smaller, int started) { // Base Case if (len == s.size()) { // If current integer has even // count of digits and is not // repeated return (mask == 0 && started); } // If current state is already // considered if (dp[mask][len][smaller][started] != -1) return dp[mask][len][smaller][started]; // Stores the maximum valid digit at // the current index int mx = 9; if (!smaller) { mx = s[len] - '0' ; } // Stores the count of valid integers int ans = 0; // If the current digit is not the // most significant digit, i.e, the // integer is already started if (started) { // Iterate through all valid digits for ( int i = 0; i <= mx; i++) { // Recursive call for ith digit // at the current index ans += calcCnt(mask ^ (1 << i), len + 1, smaller || (i < s[len] - '0' ), 1); } } else { // Recursive call for integers having // leading zeroes in the beginning ans = calcCnt(mask, len + 1, 1, 0); // Iterate through all valid digits as // most significant digits for ( int i = 1; i <= mx; i++) { // Recursive call for ith digit // at the current index ans += calcCnt(mask ^ (1 << i), len + 1, smaller || (i < s[len] - '0' ), 1); } } // Return answer return dp[mask][len][smaller][started] = ans; } // Function to calculate valid number in // the range [1, X] int countInt( int x) { // Initialize dp array with -1 memset (dp, -1, sizeof (dp)); // Store the range in form of string s = to_string(x); // Return Count return calcCnt(0, 0, 0, 0); } // Function to find the count of integers // in the range [L, R] such that the // frequency of each digit is even int countIntInRange( int L, int R) { return countInt(R) - countInt(L - 1); } // Driver Code int main() { int L = 32, R = 1010; cout << countIntInRange(L, R); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Stores the upper limit of the range static String s; // Stores the overlapping states static int [][][][] dp = new int [ 1024 ][ 10 ][ 2 ][ 2 ]; // Function to convert Integer to boolean static boolean toBoolean( int smaller) { if (smaller >= 1 ) return true ; else return false ; } // Recursive Function to calculate the // count of valid integers in the range // [1, s] using memoization static int calcCnt( int mask, int len, int smaller, int started) { // Base Case if (len == s.length()) { // If current integer has even // count of digits and is not // repeated if (mask == 0 && started != 0 ) return 1 ; else return 0 ; } // If current state is already // considered if (dp[mask][len][smaller][started] != - 1 ) return dp[mask][len][smaller][started]; // Stores the maximum valid digit at // the current index int mx = 9 ; if (smaller == 0 ) { mx = ( int )s.charAt(len) - 48 ; } // Stores the count of valid integers int ans = 0 ; // If the current digit is not the // most significant digit, i.e, the // integer is already started if (started != 0 ) { // Iterate through all valid digits for ( int i = 0 ; i <= mx; i++) { // Recursive call for ith digit // at the current index ans += calcCnt(mask ^ ( 1 << i), len + 1 , toBoolean(smaller) || (i < ( int )s.charAt(len) - 48 )? 1 : 0 , 1 ); } } else { // Recursive call for integers having // leading zeroes in the beginning ans = calcCnt(mask, len + 1 , 1 , 0 ); // Iterate through all valid digits as // most significant digits for ( int i = 1 ; i <= mx; i++) { // Recursive call for ith digit // at the current index ans += calcCnt(mask ^ ( 1 << i), len + 1 , toBoolean(smaller) || (i < ( int )s.charAt(len) - 48 )? 1 : 0 , 1 ); } } // Return answer dp[mask][len][smaller][started] = ans; return ans; } // Function to calculate valid number in // the range [1, X] static int countInt( int x) { // Initialize dp array with -1 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 ; } } } // Store the range in form of string s = Integer.toString(x); // Return Count return calcCnt( 0 , 0 , 0 , 0 ); } // Function to find the count of integers // in the range [L, R] such that the // frequency of each digit is even static int countIntInRange( int L, int R) { return countInt(R) - countInt(L - 1 ); } // Driver Code public static void main(String [] args) { int L = 32 , R = 1010 ; System.out.println(countIntInRange(L, R)); } } // This code is contributed by ihritik |
Python3
# Python program for the above approach # Stores the upper limit of the range s = "" # Stores the overlapping states dp = [[[[ 0 for _ in range ( 2 )] for _ in range ( 2 )] for _ in range ( 10 )] for _ in range ( 1024 )] # Recursive Function to calculate the # count of valid integers in the range # [1, s] using memoization def calcCnt(mask, sz, smaller, started): # Base Case if (sz = = len (s)): # If current integer has even # count of digits and is not # repeated return (mask = = 0 and started) # If current state is already # considered if (dp[mask][sz][smaller][started] ! = - 1 ): return dp[mask][sz][smaller][started] # Stores the maximum valid digit at # the current index mx = 9 if ( not smaller): mx = ord (s[sz]) - ord ( '0' ) # Stores the count of valid integers ans = 0 # If the current digit is not the # most significant digit, i.e, the # integer is already started if (started): # Iterate through all valid digits for i in range ( 0 , mx + 1 ): # Recursive call for ith digit # at the current index ans + = calcCnt(mask ^ ( 1 << i), sz + 1 , smaller or (i < ord (s[sz]) - ord ( '0' )), 1 ) else : # Recursive call for integers having # leading zeroes in the beginning ans = calcCnt(mask, sz + 1 , 1 , 0 ) # Iterate through all valid digits as # most significant digits for i in range ( 1 , mx + 1 ): # Recursive call for ith digit # at the current index ans + = calcCnt(mask ^ ( 1 << i), sz + 1 , smaller or (i < ord (s[sz]) - ord ( '0' )), 1 ) # Return answer dp[mask][sz][smaller][started] = ans return dp[mask][sz][smaller][started] # Function to calculate valid number in # the range [1, X] def countInt(x): # Initialize dp array with -1 global dp dp = [[[[ - 1 for _ in range ( 2 )] for _ in range ( 2 )] for _ in range ( 10 )] for _ in range ( 1024 )] # Store the range in form of string global s s = str (x) # Return Count return calcCnt( 0 , 0 , 0 , 0 ) # Function to find the count of integers # in the range [L, R] such that the # frequency of each digit is even def countIntInRange(L, R): return countInt(R) - countInt(L - 1 ) # Driver Code if __name__ = = "__main__" : L = 32 R = 1010 print (countIntInRange(L, R)) # This code is contributed by rakeshsahni |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Stores the upper limit of the range static string s; // Stores the overlapping states static int [,,,]dp = new int [1024, 10, 2, 2]; // Recursive Function to calculate the // count of valid integers in the range // [1, s] using memoization static int calcCnt( int mask, int len, int smaller, int started) { // Base Case if (len == s.Length) { // If current integer has even // count of digits and is not // repeated if (mask == 0 && started !=0) return 1; else return 0; } // If current state is already // considered if (dp[mask, len, smaller, started] != -1) return dp[mask, len, smaller, started]; // Stores the maximum valid digit at // the current index int mx = 9; if (smaller == 0) { mx = ( int )s[len] - 48; } // Stores the count of valid integers int ans = 0; // If the current digit is not the // most significant digit, i.e, the // integer is already started if (started !=0) { // Iterate through all valid digits for ( int i = 0; i <= mx; i++) { // Recursive call for ith digit // at the current index ans += calcCnt(mask ^ (1 << i), len + 1, Convert.ToBoolean(smaller) || (i < ( int )s[len] - 48)?1:0, 1); } } else { // Recursive call for integers having // leading zeroes in the beginning ans = calcCnt(mask, len + 1, 1, 0); // Iterate through all valid digits as // most significant digits for ( int i = 1; i <= mx; i++) { // Recursive call for ith digit // at the current index ans += calcCnt(mask ^ (1 << i), len + 1, Convert.ToBoolean(smaller) || (i < ( int )s[len] - 48)?1:0, 1); } } // Return answer dp[mask, len, smaller, started] = ans; return ans; } // Function to calculate valid number in // the range [1, X] static int countInt( int x) { // Initialize dp array with -1 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; } } } // Store the range in form of string s = x.ToString(); // Return Count return calcCnt(0, 0, 0, 0); } // Function to find the count of integers // in the range [L, R] such that the // frequency of each digit is even static int countIntInRange( int L, int R) { return countInt(R) - countInt(L - 1); } // Driver Code public static void Main() { int L = 32, R = 1010; Console.Write(countIntInRange(L, R)); } } // This code is contributed by ipg2016107. |
Javascript
// Javascript code to implement the approach // Stores the upper limit of the range var s = "" // Stores the overlapping states var dp = new Array(1024) // Function to convert Integer to boolean function toBoolean(smaller) { if (smaller >= 1){ return true } return false } // Recursive Function to calculate the // count of valid integers in the range // [1, s] using memoization function calcCnt(mask, len, smaller, started) { // Base Case if (len == s.length) { // If current integer has even // count of digits and is not // repeated if (mask == 0 && started !=0) return 1; else return 0; } // If current state is already // considered if (dp[mask][len][smaller][started] != -1) return dp[mask][len][smaller][started] // Stores the maximum valid digit at // the current index var mx = 9 if (smaller == 0) { mx = s.charCodeAt(len) - 48 } // Stores the count of valid integers var ans = 0; // If the current digit is not the // most significant digit, i.e, the // integer is already started if (started !=0) { // Iterate through all valid digits for (let i = 0 ; i <= mx ; i++) { // Recursive call for ith digit // at the current index ans += calcCnt(mask ^ (1 << i), len + 1, toBoolean(smaller) || (i < s.charCodeAt(len) - 48) ? 1 : 0, 1) } } else { // Recursive call for integers having // leading zeroes in the beginning ans = calcCnt(mask, len + 1, 1, 0) // Iterate through all valid digits as // most significant digits for (let i = 1 ; i <= mx ; i++) { // Recursive call for ith digit // at the current index ans += calcCnt(mask ^ (1 << i), len + 1, toBoolean(smaller) || (i < s.charCodeAt(len) - 48) ? 1 : 0, 1) } } // Return answer dp[mask][len][smaller][started] = ans; return ans; } // Function to calculate valid number in // the range [1, X] function countInt(x){ // Initialize dp array with -1 for (let i = 0 ; i < 1024 ; i++){ for (let j = 0 ; j < 10 ; j++){ for (let k = 0 ; k < 2 ; k++){ for (let l = 0 ; l < 2 ; l++){ dp[i][j][k][l] = -1; } } } } // Store the range in form of string s = x.toString() // Return Count return calcCnt(0, 0, 0, 0) } // Function to find the count of integers // in the range [L, R] such that the // frequency of each digit is even function countIntInRange(L, R) { return countInt(R) - countInt(L - 1); } // Driver Code var L = 32 var R = 1010 for (let i = 0 ; i < 1024 ; i++){ dp[i] = new Array(10) for (let j = 0 ; j < 10 ; j++){ dp[i][j] = new Array(2) for (let k = 0 ; k < 2 ; k++){ dp[i][j][k] = new Array(2) } } } console.log(countIntInRange(L, R)) // This code is contributed by subhamgoyal2014. |
Output:
9
Time Complexity:
Auxiliary Space:
Contact Us