Count of integers in range [L, R] having even frequency of each digit

0 0 11 minutes read

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 i^th 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:

Time Complexity: $O(2^{log_{10}R}*10)$
Auxiliary Space: $O(2^{log_{10}R}*40)$

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!