Last Updated: 19 Apr, 2021
ProRam Numbers
Hard
Asked in companies
ProRam is given an array of distinct ‘DIGITS’ sorted in ascending order. ProRam wants to know how many possible numbers can be formed from a ‘DIGITS’ array such that it is less than or equal to the given integer ‘N.' ProRam can use the digits from the ‘DIGITS’ array as many times as he wants. For Example:- ‘DIGITS’ = [1, 2, 3] . The possible numbers are 11, 1, 2, 3, 22, 221, 321, 123 etc.
ProRam is busy with some work. Can you solve this for ProRam to find the number of possible numbers formed from digit array which are less than or equal to ‘N’?
Input Format:
The first line contains ‘T,’ denoting the number of test cases.
The first line of the test case contains two integers, ‘M’ and ‘N,’ denoting the size of the ‘DIGITS’ array and given number.
The second line contains ‘M’ space-separated distinct integers denoting the elements of ‘DIGITS.’
Output Format:
For each test case, a single line should contain an integer that denotes the total possible numbers which are less than or equal to ‘N.’
Note:
You do not need to print anything, and it has already been taken care of. Just implement the given function.
Constraints:
1 <= ’T’ <= 10
1 <= ‘M’ <= 9
1 <= ‘N’ <= 10^9
1 <= ‘DIGITS[i]’ <= 9
Where ‘DIGITS’ is sorted in ascending order, and values in the ‘DIGITS’ array are unique.
Time Limit: 1 sec
Approaches
The main idea is to form all possible numbers and check if it is less than ‘N’ increase the answer by 1.
Algorithm :
- Create a variable ‘ANS’ with an initial value of ‘0’.
- Run a loop from ‘i’ equal to 1 to ‘D’ where ‘D’ is the number of digits in ‘N’.
- Inside this loop we will calculate possible numbers less equal to ‘N’ for this we create recursive function helper( ‘i’, ‘DIGITS’, ‘N’ , ‘INDEX’ = 0 ,'NUMBER' = 0).
- Inside the recursive function the base case will be if ( ‘INDEX’ == ‘i’) then return number <= ‘N’.
- In the end, return ‘ANS’ from a helper function.
- Return ‘ANS’.
Approach:- The main idea is that all possible numbers with digits less than ‘N’ are :-
- For Example :- ‘DIGITS’ = [1 ,2 ,3 ,4] , ‘N’ = 333 , ‘M’ =4
- 1 digit Numbers = (4)^1 = 4 ( By Counting Principle)
- 2 digit Numbers = (4)^2 = 16
- Thus for numbers with digits less than ‘D’ the answer will be ('M') ^ 'i' where ‘i’ is the ‘i_th’ digits.
- Now for finding number’s with digits ‘D’ we have to calculate in the following ways:-
- Number starting with 1.
- 1XX
- The possible numbers are (4)^2 by counting principle in ‘X’ any number can occur as it will be always less than 333.
- Numbers starting with 2.
- 2XX
- The possible numbers are (4)^2 by counting principle in ‘X’ any number can occur as it will be always less than 333.
- Numbers starting with 3
- 31X
- In second place any number cannot occur as it can exceed ‘N’.
- So possible numbers are
- 31X = (4)^1
- 32X
- So possible numbers are
- 32X = (4)^1.
- 33X
- In this, we cannot add anything at ‘X’ as it can exceed ‘N’.
- Thus possible numbers are 331, 332,333.
Algorithm:-
- Create a variable ‘ANS’ with an initial value of ‘0’.
- Run a loop from ‘i’ = 1 to ‘D’ - 1 where ‘D’ is the total number of digits in ‘N’ and the answer for ith digit will be ‘ANS’ += ('M') ^ ‘i’.
- Convert the ‘N' into a number array such that ‘NUMBER[i]' is ith digit from left.
- Create a recursive function helper('NUMBER', ‘DIGITS’, ‘INDEX’ = ‘0’) for finding possible numbers less than equal to ‘N’.
- Add a base case such that if ‘INDEX’ == ‘NUMBER’.length() then return ‘1’.
- Return ‘ANS’ + value from recursive function helper.
Similar problems