Numbers with product K
Posted: 29 Jun, 2021
Difficulty: Hard
Ninja Ankush likes to brag that he is the Ultimate Ninja among his peers. Therefore his fellow Ninja Nikhil gave him a riddle to check if Ankush is really the Ultimate Ninja. Nikhil gave Ankush a range and a number ‘K’, and asked how many numbers exist in the range such that the product of the digits of the number is equal to ‘K’. Help Ninja Ankush to prove to Ninja Nikhil that he, in fact, is the Ultimate Ninja.
More Formally, Given three positive integers ‘L’, ‘R’ and ‘K’, the task is to count the numbers in the range ‘L’ and ‘R’ inclusive, whose product of digits is equal to ‘K’.
For example
Given:
‘L’ = 1, ‘R’ = 23, ‘K’ = 6.
The answer will be 3 since there are three numbers between 1 and 23 whose product of digits is 6, and those are 6, 16, and 23.
Input format:
The first line of input contains an integer ‘T’ denoting the number of test cases.
Next, ‘T’ lines consist of three space-separated integers, ‘L’, ‘R’, ‘K’.
Output Format :
For each test case, return the count of numbers between ‘L’ and ‘R’ whose product of digits is ‘K’.
Note:
You are not required to print the expected output; it has already been taken care of. Just implement the function.
Constraints:
1 <= ‘T’ <= 10
1 <= ‘L’ <= 10 ^ 8
‘L’ <= ‘R’ <= 10 ^ 8
1 <= ‘K’ <= 10 ^ 4
Time Limit: 1sec.
Approach 1
The idea is to traverse from ‘L’ to ‘R’ and check for each number if the product of the digits of the number is equal to ‘K’.
The steps are as follows:
- Maintain a variable ‘cnt’ which maintains the count of numbers if the product of the digits of the number is equal to ‘K’.
- Loop from ‘L’ to ‘R’ using variable ‘i’:
- For each ‘i’, check if it satisfies the condition. To check, we will use a helper function ‘isIt’.
- ‘isIt’ takes ‘i’ and ‘K’ as input parameters and returns a boolean value denoting if it satisfies the condition.
- Convert ‘i’ to string using the inbuilt function ‘to_string’, which converts an integer into a string.
- Traverse the string and multiply each character’s integer value into ‘product’ which stores the product of all digits of the string.
- If ‘product’ is equal to ‘K’ return true, else return false.
- If ‘isIt’ returns true, increase the ‘cnt’ by 1 and continue.
- Return ‘cnt’ as the final answer.
Approach 2
The idea is to observe that the answer is :
Count of numbers that satisfy conditions from 0 to ‘R’ - Count of numbers that satisfy conditions from 0 to ‘L - 1’.
This can be done by calculating these two quantities separately and then returning the answer. Since we are using recursion, our states will depend on the following parameters:
- ‘idx’: It tells about the index value from right in the given integer.
- ‘tight’: This will tell if the current digits range is restricted or not. If the current digit’s range is not restricted, then it will span from 0 to 9 (inclusively) else, it will span from 0 to ‘num’[idx] (inclusively).
- ‘product’: The product of digits from 0 to the ‘idx’.
- ‘leadingZero’: Whether for the given configuration, there exists leading zeros or not.
The steps are as follows:
- For each of the above problems, we will use a helper function ‘numsWithProductKhelper’, which takes string ‘num’, ‘idx’, ‘product’, ‘K’ and ‘tight’ as input parameters, where:
- ‘num’ is the integer value converted into a string,
- ‘idx’ denotes the index of the string ‘num’,
- ‘product’ denotes the product of numbers till ‘idx’ in ‘num’
- ‘tight’ denotes whether we are constrained by the initial number.
- ‘leadingZeros’ to tell whether the number has leading zeros.
- It is a recursive function. Therefore the base condition is if we have reached the end of the string, then check if the ‘product’ is equal to ‘K’ then return 1, else if ‘product’ is greater than or less than ‘K’ return 0.
- To check the upper bound of the current ‘idx’ we check ‘tight’ if ‘tight’ is 0, then the upper bound(denoted by ‘end’) will be 9, else it will be ‘num[idx]’ - ‘0’.
- Maintain a variable ‘res’, which stores the total count.
- Traverse from 0 to ‘end’ using variable ‘dig’:
- If ‘dig’ is zero and ‘leadingZero’ is true, then we recur for ‘idx + 1’, ‘product’,and (‘tight’ & ‘dig’ == ‘end’), and keep ‘leadingZero’ as true.
- Else we recur for the state as ‘idx + 1’, ‘product * dig’, ‘tight & dig’ == ‘end’ and turn ‘leadingZero’ to false.
- We store the answers from both of these sub-problems in ‘res’.
- Return ‘res’ as the final answer.
Approach 3
The idea is to observe that the answer is :
Count of numbers that satisfy conditions from 0 to ‘R’ - Count of numbers that satisfy conditions from 0 to ‘L - 1’.
This can be done by calculating these two quantities separately and then returning the answer. Since we are using recursion, our states will depend on the following parameters:
- ‘idx’: It tells about the index value from right in the given integer.
- ‘tight’: This will tell if the current digits range is restricted or not. If the current digit’s range is not restricted, then it will span from 0 to 9 (inclusively). Else it will span from 0 to ‘num’[idx] (inclusively).
- ‘product’: The product of digits from 0 to the ‘idx’.
- ‘leadingZero’: Whether for the given configuration, there exists leading zeros or not.
We can see that since there are multiple states, there will be repeated sub-problems for which we recur repeatedly, therefore to speed up recursion we can hash repeating sub-problems by maintaining a ‘dp’ array which stores the answer for given states.
The steps are as follows:
- Maintain a ‘dp’ array where ‘dp[product][idx][tight][leadingZeros]’ represents the count of numbers with ‘product’ till ‘idx’ under ‘tight’ and ‘leadingZeros’ condition which satisfy the condition.
- For each of the above problems, we will use a helper function ‘numsWithProductKhelper’, which takes string ‘num’, ‘idx’, ‘product’, ‘K’ and ‘tight’ as input parameters and ‘dp’ array, where:
- ‘num’ is the integer value converted into a string,
- ‘idx’ denotes the index of the string ‘num’,
- ‘product’ denotes the product of numbers till ‘idx’ in ‘num’
- ‘tight’ denotes whether we are constrained by the initial number.
- ‘leadingZeros’ to tell whether the number has leading zeros.
- It is a recursive function. Therefore the base condition is if we have reached the end of string, then check if the ‘product’ is equal to ‘K’ then return 1, else if ‘product’ is greater than or less than ‘K’ return 0.
- If we have already visited this state, return ‘dp[product][idx][tight][leadingZeros]’.To check the upper-bound of for the current ‘idx’ we check ‘tight’ if ‘tight’ is 0, then the upper bound(denoted by ‘end’) will be 9, else it will be ‘num[idx]’ - ‘0’.
- Maintain a variable ‘res’, which stores the total count.
- Traverse from 0 to ‘end’ using variable ‘dig’:
- If ‘dig’ is zero and ‘leadingZero’ is true, then we recur for ‘idx + 1’, ‘product’,and (‘tight’ & ‘dig’ == ‘end’), and keep ‘leadingZero’ as true.
- Else we recur for the state as ‘idx + 1’, ‘product * dig’, ‘tight & dig’ == ‘end’ and turn ‘leadingZero’ to false.
- We store the answers from both of these sub-problems in ‘res’ and assign dp[product][idx][tight][leadingZeros] = ‘res’ to hash the current state for future use.
- Return ‘res’ as the final answer.
