Find Count of numbers from a given range whose product of digits is X

Brute Force Approach

The simplest way to tackle this problem is to loop over all of the numbers in the range [S, E], checking whether or not their product of digits equals 'X.' If this is proven to be true, the ‘count’ variable should be increased. Finally, print the total ‘count’. Below is the implementation for the given approach.

Algorithm 

1. Start by defining a function called ‘ProductInRange’ that takes three integer inputs: S (representing the starting index), E (representing the ending index), and X (representing the product).
    
2. Initialize a counter variable ‘count’ to 0.
    
3. Use a for loop to iterate through all the integers between S and E, inclusive.
   • Within the for loop, initialize a variable called ‘product’ to 1.
      
   • Initialize a variable called ‘n’ to the value of the current integer in the for loop.
      
   • Use a while loop to iterate through each digit of ‘n’, from right to left.
      
   • Within the while loop, multiply product by the current digit of ‘n’.
      
4. After the while loop has completed, check if product is equal to X.
    
5. If product is equal to X, increment the count variable by 1.
    
6. After the for loop has completed, return the value of ‘count’.

Dry Run

1. Here, count = 0, S = 1, E = 50, and X = 12.
    
2. Now, move to the for loop in the ‘ProductInRange’ function and initialize product to 1.
    
3. For every number from 1 to 50 (both inclusive), execute the while loop.
   1. For i = 1, the while loop executes as follows:
      • n = 1
      • product = (1 % 10) = 1
      • n = 0 (because 1 / 10 = 0 with integer division)
      • Since product ((i.e., product of digits in 1) is not equal to X (12), count remains 0.
         
   2. For i = 2, the while loop executes as follows:
      • n = 2
      • product = (2 % 10) = 2
      • n = 0 (because 2 / 10 = 0 with integer division)
      • Since product ((i.e., product of digits in 2) is not equal to X (12), count remains 0.
         
   3. Let’s take i = 26, the while loop executes as follows:
      • n = 26
      • product = (26 % 10) = 6
      • n = 2 (because 26 / 10 = 2 with integer division)
      • product = (2 % 10) = 6 * 2 = 12
      • Therefore product (i.e., product of digits in 26) is equal to X (12), count is incremented by 1.
         
   4. Let’s take i = 34, the while loop executes as follows:
      • n = 34
      • product = (34 % 10) = 4
      • n = 3 (because 34 / 10 = 3 with integer division)
      • product = (3 % 10) = 4 * 3 = 12
      • Therefore product ((i.e., product of digits in 34) is equal to X (12), count is incremented by 2.  
         
   5. Let’s take i = 43, the while loop executes as follows:
      • n=43
      • product = (43 % 10) = 3
      • n = 4 (because 43 / 10 = 4 with integer division)
      • product = (4 % 10) = 3 * 4 = 12
      • Therefore product ((i.e., product of digits in 43) is equal to X (12), count  is incremented by 3.  
         

4. We would not find any more numbers with X=12 from the numbers 1 to 50. Hence the output is returned as 3.

Code in C++

#include <iostream>
using namespace std;

/* 
    This function counts the number of integers 
    between S and E whose digits multiply to X.
*/
int ProductInRange(int S, int E, int X) {
    int count = 0;
    /* 
        Initialize product to 1 and Multiply the digits 
        of the number i using the while loop
        If the product equals X, increment the count
    */
    for (int i = S; i <= E; i++) {
        int product = 1;  
        int n = i;
        while (n) { 
            product *= (n % 10);
            n /= 10;
        }
        
        if (product == X) {  
            count++;
        }
    }
    // Return the count
    return count;  
}

int main() {
    // Start of the range
    int S = 1; 
    // End of the range
    int E = 50;  
    // Product we are looking for
    int X = 12; 
    /* 
        Count the number of integers
        whose digits multiply to X. 
    */
    int count = ProductInRange(S, E, X);  
    // Print the result
    cout << count << '\n';  
    return 0; 
}

You can also try this code with Online C++ Compiler

Run Code

Output

Complexity

Time Complexity 

O(E – S + 1) * log₁₀(E) 

The time complexity is O(E – S + 1) * log₁₀(E). Since we are linearly iterating from range S to E and in every iteration, we are calculating the product of the number. To calculate the product of a number, we are linearly iterating on all the digits of a number which will cost logarithmic time complexity.

Space Complexity 

O(1)

The space complexity is O(1) since we have not used any extra space in the entire implementation.

Dynamic Programming Approach

To optimize the given approach, we need to use the digit DP concept. Given is the state of the dp array. The given code implements a recursive approach to count the number of integers in a given range that have a specific target product. The function uses memoization to avoid redundant computations and returns the difference between the counts of such numbers in the ranges [0, E] and [0, S-1].

Algorithm 

1. Define a constant MAX_DIGITS as 100 and declare a 4D memoization array memo of size MAX_DIGITS x MAX_DIGITS x 2 x 2 to store previously computed results.
    
2. Define a recursive function “countTarget” that takes six arguments: ‘num’, ‘index’, ‘productSoFar’, ‘targetProduct’, ‘atStart’ and ‘exceeds’. 
   • The variable ‘num’ is the string representation of the number being considered, ‘index’ is the current index being considered, ‘productSoFar’ is the product of the digits seen so far, and ‘targetProduct’ is the target product value. 
      
   • The function also takes two boolean parameters: ‘atStart’ and ‘exceeds’. ‘atStart’ is set to true only for the first digit, while ‘exceeds’ indicates whether the product so far has exceeded the target product.
      
3. Check if the current state has been computed previously by checking the memoization array. If the state exists, return the memoized result.
    
4. If the index is greater or equal to the length of the input number or if the product so far is greater than the target product.
   • If the product so far equals the target, return 1.
      
   • Else, 0 otherwise.
      
5. Initialize a ‘count’ variable to 0.
    
6. Calculate the maximum digit for this recursion based on whether ‘exceeds’ is true or false. If ‘exceeds’ is true, set the end to the current digit. Otherwise, set it to 9.
    
7. Loop over all possible digits for this recursion.
   • If the current digit is 0 and we are not at the start of the number, recurse on the next digit without changing the product so far.
      
   • If the current digit is not 0 or we are at the start of the number, recurse on the next digit while multiplying the product so far by the current digit.
      
8. Add the result of the recursive call to the count variable.
    
9. Memoize the computed result and return the count.
    
10. Define the “ProductInRange” function that takes three arguments: S, E, and X. 
    ‘S’ and ‘E’ are bounds of the range to be considered, while ‘X’ is the target product value.
     
11. Convert the lower and upper bounds to strings and initialize the memoization array memo to store previously computed results.
     
12. Count the numbers with target product less than X in the range [0, S-1] by calling countTarget with num = str1, index = 0, productSoFar = 1, targetProduct = X, atStart = false, and exceeds = true.
     
13. Initialize the memoization array memo to -1.
     
14. Count the numbers with target product less than X in the range [0, E] by calling countTarget with num = str2, index = 0, productSoFar = 1, targetProduct = X, atStart = false, and exceeds = true.
     
15. Return the difference between the two counts, which gives the count of numbers with target product less than X in the range [S, E].

Dry Run

1. Initialize the bounds as strings:
   • str1 = to_string(S - 1) = "0"
   • str2 = to_string(E) = "50"
   • Initialize the memoization array to -1.
      
2. Count the numbers with target product less than X in the range [0, S-1] = [0, 0] using countTarget function.
    
3. The countTarget function is called with the following arguments:
   • Set index = 0, (the starting index of the string) 
   • num = the string representation of str1 whose length is 1.
   • productSoFar = 1, the product of the digits seen so far which is 1.
   • targetProduct = 12, the target product which is X=12.
   • atStart = false, boolean to tell whether we are at the start of the number.
   • exceeds = true. Boolean if we have exceeded the upper bound of the range.
      
4. Check if index >= num.length() (since index = 0 < num = 1) or productSoFar > targetProduct (since productSoFar = 1 < targetProduct = 12) which is not true.
    
5. Check if memo[productSoFar][index][atStart][exceeds] has been computed before, which is not true.
    
6. If the digit considered is 0, a recursive call is made with the same arguments except the ‘atStart’ is set to false, since we are no longer at the start of the number.
    
7. The memoization array is made with all the recursive calls and count is returned which is 0 in this case as there is no number from [0,0] with product of numbers equal to 12.
    
8. Now we need to repeat the steps 2-7 for str2 = “50” instead of str1 = “0”.
    
9. Memoize the result in memo[productSoFar][index][atStart][exceeds] and return count = 3.
    
10. Return the difference between the two counts which is 3.

Code in C++

#include <iostream>
#include <cstring>
#include <string>

using namespace std;

const int MAX_DIGITS = 100;
// 4D memoization array
int memo[MAX_DIGITS][MAX_DIGITS][2][2]; 

// Recursive function to count the numbers with target product
int countTarget(string num, int index, int productSoFar, int targetProduct, bool atStart, bool exceeds) {
    /*
        If the index is greater than or
        equal to the length of the input number
    */
    /* 
        If the product so far is greater than the 
        target product, return 1 if the product so far
        equals the target, 0 otherwise
    */
    if (index >= num.length() || productSoFar > targetProduct) {
        return (productSoFar == targetProduct);
    }

    // Check if this state has already been computed
    if (memo[productSoFar][index][atStart][exceeds] != -1) {
        return memo[productSoFar][index][atStart][exceeds];
    }

    // Initialize the count variable to 0
    int count = 0; 
    // Calculate the maximum digit for this recursion
    int end = exceeds ? num[index] - '0' : 9; 

    // Loop over all possible digits for this recursion
    for (int digit = 0; digit <= end; digit++) {
        /*
            If the current digit is 0 and 
            we are not at the start of the number.
            Recurse on the next digit without
            changing the product so far. Else, 
            recurse on the next digit while multiplying
            the product so far by the current digit
        */
        if (digit == 0 && !atStart) { 
            
            count += countTarget(num, index + 1, productSoFar, targetProduct, false, (exceeds && (digit == end)));
        }
        
        else { 
            
            count += countTarget(num, index + 1, productSoFar * digit, targetProduct, true, (exceeds && (digit == end)));
        }
    }
    
    // Memoize the computed result
    memo[productSoFar][index][atStart][exceeds] = count;
    // Return the count
    return count; 
}

/*
    Function to count the numbers with 
    target product in the given range
*/
int ProductInRange(int S, int E, int X) {
    // Convert the lower and upper bounds to strings
    string str1 = to_string(S - 1);
    string str2 = to_string(E);

    // Initialize the memoization array to -1
    memset(memo, -1, sizeof(memo)); 
    /*
        Count the numbers with target product
        equal to X in the range [0, S-1]
    */
    int count1 = countTarget(str1, 0, 1, X, false, true); 

    // Reset the memoization array to -1
    memset(memo, -1, sizeof(memo)); 
    /*
        Count the numbers with target product 
        equal to X in the range [0, E]
    */
    int count2 = countTarget(str2, 0, 1, X, false, true); 

    // Return the difference between the two counts
    return (count2 - count1); 
}

// Main function
int main() {
    int S = 1, E = 50, X = 12;
    // Call the function and print the result
    cout << ProductInRange(S, E, X) << endl; 
    return 0; 
} 

You can also try this code with Online C++ Compiler

Run Code

Output

Complexity

Time Complexity 

O(X * log(E) * 2 * 2 * 10)

The time complexity is O(X * log(E) * 2 * 2 * 10). Since we are trying to fill a 4d dp array of which has arguments as a product of a number and X and two boolean parameters. So to fill this entire dp array total time complexity will be O(2 * 2 * (product of num) * (X) * 10) where to calculate the product of num for the last Number in range will be O(log(E)) hence time complexity will be around O(X * log(E) * 2 * 2 * 10).

Space Complexity 

O(X * log(E) * 4)

The space complexity is O(X * log(E) * 4) space complexity since we are creating a 4d dp array to store the results of previously computed range.

Frequently Asked Questions 

What is the product of digits of a number?

It is defined as the result obtained by multiplying all the digits of the number.

What is dynamic programming?

It is a method of solving complex problems by breaking them down into smaller, simpler subproblems and solving each subproblem only once.

What is memoization?

Memoization is a method of storing the outcomes of computationally expensive function calls and retrieving the cached results when the function is called again with the same inputs.

What is the STL function to convert int to string?

We can use the ‘to_string’ STL function in C++ to convert int to string.

What is the range of numbers?

The range of numbers is a set of numbers between a given minimum and maximum value.

Conclusion

In this blog, we learned the count and say problem. We have implemented the problem in C++ programming language.

For more string data structure articles, you can refer following links:

• Compress the string
• Encode and Decode
• Edit distance
   

To learn more about DSA, competitive coding, and many more knowledgeable topics, please look into the guided paths on Coding Ninjas Studio. Also, you can enroll in our courses and check out the mock test and problems available to you. Please check out our interview experiences and interview bundle for placement preparations.

Happy Coding!