Numbers with product K

Posted: 29 Jun, 2021
Difficulty: Hard


Try Problem

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

‘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’.
You are not required to print the expected output; it has already been taken care of. Just implement the function.
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.
Try Problem