Do you think IIT Guwahati certified course can help you in your career?
Introduction
Dynamic programming is one of the most challenging ideas to learn at first, but it becomes very simple once you get the hang of it. The most basic technique for becoming proficient in DP is to improve learning by identifying patterns in the problems. In this article, we'll look at one such fantastic problem: a version of Digit DP. So, let's get this party started.
Problem Statement
Given a range [ L, R ] and an integer K, you have to return the count of numbers in the range [ L, R ] whose product of digits is K.
Example:
Input: L=10, R=100, K=14
Output: 2
Explanation: 27 => 2 * 7 = 14
72 => 7 * 2 = 14
As when we multiply the digits of 27 and 72, we get 14, i.e., K
Now that you have understood the problem, it is always a good idea to try it yourself. Try solving the problem here and return if you get stuck or need more explanation.
Approach 1 - Brute Force
First, let's see the brute force approach for the problem. In this, you can iterate over the range from L to R and check for each number if the product of digits is K, then increment the count.
This one is pretty intuitive and not much of magic. However, you should be aware of it for one reason: it's easy, and you should know it :).
Program
#include <iostream>
using namespace std;
// Function to check whether the product of digits of X is equal to K or not.
bool isProductK(int x, int k)
{
int p = 1;
// Calculate the product of digits.
while (x != 0)
{
p *= (x % 10);
x /= 10;
}
// Check if the product is equal to K.
if (p == k)
return true;
return false;
}
int countProductK(int l, int r, int k)
{
int count = 0;
for (int i = l; i <= r; i++)
{
// If the product of digits is K, increment the COUNT.
if (isProductK(i, k))
{
count++;
}
}
return count;
}
int main()
{
int l, r, k;
cout << "Enter the value of L, R, and K\n";
cin >> l >> r >> k;
int count = countProductK(l, r, k);
cout << "Count of Numbers in range [L:" << l << ", R:" << r << "] whose product of digits is K: " << K << " = " << count << endl;
return 0;
}
You can also try this code with Online C++ Compiler
Count of Numbers in the range [L:10, R:50] whose product of digits is K: 12 = 3
Time Complexity
O((log(R!) / (L-1)!), where L and R are the integer ranges.
The time complexity of countProductK() function is dependent on the number of times isProductK() function is called. The time complexity of the isProductK() function is log(N) for input N, as there are log(N) digits in an integer N.
Since the isProductK() function is called for every value between ‘L’ and ‘R’, the time complexity of countProductK() function is
Since we are not using any auxiliary space, space complexity is O(1).
Approach 2 - Recursion + Memoization
As can be observed, the brute force method takes a long time, and it is impossible for R=[10^15 - 10^18] to be solved by brute force. This problem can also be solved using the concept of Digit DP, which will significantly reduce our time complexity. But how would someone address this problem with Digit DP? Let's have a look.
Visit this blog for a quick overview of Digit DP.
We’ll try to build a recursive solution first and then try to add memoization. Consider the following example
L = 10, R = 250, K = 14
Between 10 and 250, numbers whose digits product is 14 are - { 027, 072, 127, 217 }
So we need to find all three-digit numbers whose digits product is 14.
Note: Two and one-digit numbers can also be written as three-digit numbers by appending zeros at the beginning.
We can choose from 0 to 9 for all three digits. That is, we will choose a digit for each position and then recurse for the other digits to build the product equal to 14.
To start, let's define the basic recurrence relation.
F(COUNT_DIGITS, PROD) = F(i-1, PROD/x) for all x (0 to 9)
where COUNT_DIGITS = number of digits and PROD = product.
We are not managing the boundary in the above recurrence, i.e., the number generated by the selected digits X < R.
Example
If R = 57529, we have to choose 5 digits.
For the first digit, if we choose any number greater than equal to 6, then no matter what the other four digits are, the number formed will be invalid, i.e., greater than R. So for the first digit, we can choose from 0 to 5 (this is where ON_EDGE = true )
If the first digit is in the range of 0 to 4, then the second digit can be anywhere from 0 to 9. For example, 49999 is a valid number.
But if the first digit is 5 (boundary), then the second digit should be less than equal to 7 (second digit in R= 57529). This is where ON_EDGE = true
The number formed by the digits should lie in the colored area.
Conclusion
If the ‘i’th digit is on edge, then the (i + 1)th digit range is reduced to 0 to the (i + 1)th digit in R.
Hence ON_EDGE will tell us if there’s a possibility of exceeding R in the future.
Another important observation is that if we choose 0, our product will be zero unless they are leading zeros (for forming one and two-digit numbers).
Example
If R= 217, we have to find all numbers from 0 to 217 whose product of digits is K.
For all one-digit numbers first two digits will be zero, and for two-digits numbers, the first digit will be zero. Now in both these cases, the zeros are leading zeros. For example, 001, 002, 022, etc.
But if we choose zero, which is not a leading zero, the product will become zero. For example, In 020, third zero and in 205, second zero will make the product zero.
Hence, LEADING_ZEROS will tell us if we can append zero to the number.
Now that we've gone over the essential features let's code the recursive solution.
Program for Recursive Approach
#include <iostream>
using namespace std;
// Maxximum digits in R.
#define M 100
int digitDP(string num, int i, int prod, int K, bool leadingZeros, bool onEdge)
{
// Checking if the number of digits selected exceeds the number of digits in number OR product exceeds K => BASE CASE.
if (i >= num.length() || prod >= K)
{
// Return true if the product of digits is K else return false.
return prod == K;
}
int ans = 0;
int range = 9;
if (onEdge)
range = num[i] - '0';
for (int x = 0; x <= range; x++)
{
// Check if the number has leading zeros then we can add another zero.
if (x == 0 && !leadingZeros)
{
ans += digitDP(num, i + 1, prod, K, false, (onEdge & (x == range)));
}
else
{
ans += digitDP(num, i + 1, prod * x, K, true, (onEdge & (x == range)));
}
}
// Return the ans.
return ans;
}
int countProductK(int l, int r, int k)
{
// Converting the numbers into string.
string lS = to_string(l - 1);
string rS = to_string(r);
// Count all numbers from 0 to L whose digits product is K.
int left = digitDP(lS, 0, 1, k, false, true);
// Count all numbers from 0 to R whose digits product is K.
int right = digitDP(rS, 0, 1, k, false, true);
// Digits in range L to R is count(R)-count(L).
return right - left;
}
int main()
{
int l,r,k;
cout << "Enter value of L,R and K\n";
cin >> l >> r >> k;
int count = countProductK(l, r, k);
cout << "Count of Numbers in range [L:" << l << ", R:" << r << "] whose product of digits is K:" << k << "= " << count << endl;
return 0;
}
You can also try this code with Online C++ Compiler
Count of Numbers in the range [L:10, R:50] whose product of digits is K:12= 5
Time Complexity
O(10^(log(R)), where R = Upper Bound.
Since the number of digits in R = log10(R) and for each digit we can choose from 0 to 9, so our time complexity is 10^(log(R)).
Space Complexity
O(1), as we are not using any extra space.
Now let's look at why and how dynamic programming can be used to solve this problem.
There are two possible arrangements of digits 2,1,7 with product 14 in the range [10, 250]: 217 and 127. For finding the first digit, we will iterate over 0 - 9 and choose one and then find the next digit. So if we choose 1 and then 2, we will have to find one digit with product 7 similarly. If we choose 2 and then 1, we will have to find one digit with product 7. Subproblems will repeat.
Let’s jump to code.
Program for Memoized Approach
#include <iostream>
using namespace std;
// Maxximun digits in R.
#define M 100
int digitDP(string num, int i, int prod, int K, bool leadingZeros, bool onEdge, unordered_map<string, int> &dp)
{
// Checking if a number of digits selected exceed the number of digits in the number.
// Or product exceeds K => BASE CASE.
if (i >= num.length() || prod >= K)
{
// Return true if Product of digits is K else return false.
return prod == K;
}
// Creating key for memoization.
string key = to_string(prod) + " " + to_string(i) + " " + to_string(onEdge) + " " + to_string(leadingZeros);
// Check if we have already computed the results.
if (dp.find(key) != dp.end())
{
return dp[key];
}
int ans = 0;
int range = 9;
if (onEdge)
range = num[i] - '0';
for (int x = 0; x <= range; x++)
{
// Check if number has leading zeros.
if (x == 0 && !leadingZeros)
{
ans += digitDP(num, i + 1, prod, K, false, (onEdge & (x == range)), dp);
}
else
{
ans += digitDP(num, i + 1, prod * x, K, true, (onEdge & (x == range)), dp);
}
}
// Store the result in map and return.
return dp[key] = ans;
}
int countProductK(int l, int r, int k)
{
// Converting nuber into string.
string lS = to_string(l - 1);
string rS = to_string(r);
// This is to memoize.
unordered_map<string, int> dp;
// Count all numbers from 0 to L whose digits product is K.
int left = digitDP(lS, 0, 1, k, false, true, dp);
dp.clear();
// Count all numbers from 0 to R whose digits product is K.
int right = digitDP(rS, 0, 1, k, false, true, dp);
// Digits in range L to R is count(R)-count(L).
return right - left;
}
int main()
{
int l, r, k;
cout << "Enter the value of L,R, and K\n";
cin >> l >> r >> k;
int count = countProductK(l, r, k);
cout << "Count of Numbers in range [L:" << l << ", R:" << r << "] whose product of digits is K: " << k << "= " << count << endl;
return 0;
}
You can also try this code with Online C++ Compiler
Count of Numbers in the range [L:10, R:50] whose product of digits is K:12= 3
Time Complexity
O(K*log(R)*10*4), where K = product, R = Upper Bound.
Since we are recurring until the PRODUCT is K.
No of digits in R = log10(R)
No of digits to choose from = 10 (0 to 9)
And the total combination of ON_EDGE and LEADING_EDGE variable = 4 (11, 00, 01, 10)
So Time complexity = K*log(R)*10*4
Space Complexity
O(K*log(R)*4), where K = Product, R = Upper Bound.
Key Takeaways
By solving the above problem, we learned how to approach a problem in an interview. Start with the brute force and then build up your solution, discuss the time complexity and tradeoffs of one solution over the other. Once you’re done with the solution idea, decide what functions you need and define and what they will do. Next, trust other functions will do their job and focus on one function and what it must do.
Many Big tech companies ask questions from this class of dynamic problems that is Digit DP. Try solving other variations of this problem. Coding ninjas have a wide range of problems in DP. Do check it out.
24+ registered 
