Magical Digits

Ninja
0/200
Average time to solve is 31m
profile
Contributed by
0 upvote

Problem statement

Professor Sergio is researching numbers. In particular, he is interested in magical numbers. For a given array ‘A’ of size 10 (A[0], A[1], ….., A[9]), he considers all the integers ‘i’ as magical if there exists some digit ‘D’ which occurs exactly A[D] times in the decimal representation of ‘i’ without leading zeros. Now given two integers ‘L’ and ‘R’, and array ‘A’. You are required to count the number of non-magical numbers in the range [L, R] both inclusive.

For Example: 
Range = [17, 25], A = [4, 2, 1, 3, 4, 5, 9, 7, 1, 5]

Magical numbers in the given range are
18, has 8 A[8] = 1 time.
20, has 2 A[2] = 1 time.
21, has 2 A[2] = 1 time.
23, has 2 A[2] = 1 time.
24, has 2 A[2] = 1 time.
25, has 2 A[2] = 1 time.
All the remaining numbers in the range are non-magical, i.e., 17, 19, and 22.
We have three non-magical elements for ‘A’ in the given range. So the output will be 3.
Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of the input contains a single integer ‘T’ representing the no. of test cases.

The first line of each test case contains two space-separated integers, ‘L’ and ‘R’, denoting the range on which we have to count non-magical numbers.

The second line of each test case contains 10 space-separated integers, denoting the elements of ‘A’.

Output Format:

For each test case, print a single integer value denoting the number of non-magical numbers for ‘A’ in the given range. 

Print a separate line for each test case.
Note: 
You are not required to print anything; it has already been taken care of. Just implement the function and return the answer.

Constraints:

1 ≤ T ≤ 100
1 ≤ L ≤ R ≤ 10^9
0 ≤ A[i] ≤ 9
A.length = 10

Time limit: 1 Sec
Sample Input 1 :
2
17 25
4 2 1 3 4 5 9 7 1 5
83 85
3 1 2 3 4 5 6 7 0 0
Sample Output 1 :
3
0
Explanation For Sample Input 1 :
For First Case - Same as explained in above example.

For the second case - 

Range = [83, 85], A = [3, 1, 2, 3, 4, 5, 6, 7, 0, 0]

Magical numbers in the given range are
83, has 9 A[9] = 0 time.
84, has 9 A[9] = 0 time.
85, has 9 A[9] = 0 time.
All numbers in the range are magical. So we don’t have any non-magical elements for ‘A’ in the given range. So the output will be 0.
Sample Input 2 :
2
124 185
2 1 4 2 6 3 3 8 9 4
8 36
5 1 7 3 5 2 1 8 5 0
Sample Output 2 :
6
2
Hint

Can we check for all values in the given range?

Approaches (2)
Brute Force

We can iterate on all the integers in the given range of L to R. For every integer ‘i’ we can calculate the frequency of its digits, and if any of the digits’ frequency matches that in the given array ‘A’, then ‘i’ is a magical number, otherwise it isn’t. Implementation details are as per the following algorithm.

 

Algorithm:


Given Function

  • Declare and initialize integer ans = r-l+1
  • Iterate over i from l to r
    • Declare and initialize integer n = i
    • Declare frequency array of size 10 initialized to all zeros
    • While n > 0
      • Increment freq[n % 10]
      • Divide n by 10
    • Iterate over j from 0 to 9
      • If a[j] == freq[j]
        • Decrement ans
        • Break
  • Return ans
Time Complexity

O(R - L) where [L, R] is the given range.

 

We are iterating over every integer in the range, which is of order O(R - L). Each integer takes O(1) time to check whether it is magical or not. So, total time will be O(R - L) * O(1) = O(R - L).

Space Complexity

O(1)

 

We only need extra space for the ans and frequency array. These are constant in size and take O(1) storage. So total space required will be O(1).

Code Solution
(100% EXP penalty)
Magical Digits
Full screen
Console