Numbers with product K

Hard
0/120
Average time to solve is 50m
profile
Contributed by
5 upvotes
Asked in companies
DirectiCodenation

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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.

Sample Input 1 :

2
1 23 6
11 25 2

Sample Output 1 :

3
2

Explanation of the Sample Input 1:

In the first test case, The answer will be 3 since there are 3 numbers between 1 and 23 whose product of digits is 6, and those are 6, 16, and 23.

In the second test case, The answer will be 2 since there are 2 numbers between 1 and 25 whose product of digits is 2, and those are 12, 21.

Sample Input 2 :

2
3 23 3
4 50 9

Sample Output 2 :

2
3
Hint

Can we iterate over all the numbers and check for each number?

Approaches (3)
Naive Solution

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.
Time Complexity

 O((R - L) * log(R)), Where ‘R’ and ‘L’ are the integers given to us.

 

Since we are traversing from ‘R’ to ‘L’ and each number in between can have at max log10(R) digits. Therefore the overall time complexity will be O((R - L) * log(R)).

Space Complexity

O(1).


 

Since we are not using any extra space.

Code Solution
(100% EXP penalty)
Numbers with product K
Full screen
Console