Magical Digits

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

We can use the inclusion-exclusion principle for this problem. Let mask be an integer whether if the ith bit of mask is set, then it will mean that number of i's in the decimal representation of the number is a[i]. Note that this doesn’t put any condition on the mask bits that are not set. Their count could potentially be equal to corresponding a[i] too. The set of masks with an odd number of set bits should be added to the answer, and those of even set bits should be subtracted from the answer.

Our problem turns into finding the count of numbers in the [0, n] where you are also provided an integer mask denoting where the corresponding set bits put a condition on the count of the corresponding digit’s count.

A number in the range [0, n] will follow this structure. It will have some prefix common with n, then the next digit is less than the corresponding digit of n, and then the remaining numbers could be anything. So, we iterate over each possible length of the largest common prefix from 1 to 9 (as n can be at most 10^9), then we iterate over the next digit from 0 to the corresponding digit of n. We can check the count of digits that have appeared till now. We can find the number of their occurrences for the set bits, which should be a part of the upcoming part of the number being constructed. The count of some number i with ith bit set of masks might have its number of occurrences greater than a[i], which will mean that the constructed number is already invalid, and we should not proceed with it further. We can use simple combinatorics to find the number of ways to fill the remaining digits.

One possible issue that might come in implementation is to take care of leading zeros properly. Assume that length of the common prefix of the number being generated is zero, i.e., the first digit is 0. You should count such cases carefully. Implementation details are as per the following algorithm.

Algorithm:

Count function

Function arguments - integer ‘N’ representing no. of digits available, integer array ‘needed’

Returns - Number of integers formed using needed and free digits.

• Declare and initialize sum = 0
• Iterate over every integer i in needed
  • Add i to sum
• Declare and initialize integers remaining = 10 - size of needed, extra = n - sum
• If extra < 0
  • Return 0
• Declare fact array for storing factorials with a single element equal to 1.
• Iterate over i from 1 to 9
  • Append (last element of fact * i) to fact
• Declare and initialize integer ans = fact[sum]
• Iterate over every integer i in needed
  • Divide ans by fact[i]
• Multiply ans by fact[n] / (fact[extra] * fact[n-extra])
• Iterate over i from 1 to extra
  • Multiply ans with remaining
• Return ans

fillAnyDigits function

Function arguments - integer array ‘mask’, given array ‘a’, integer ‘start’, integer ‘end’, integer ‘digitsAvailable’

Fills any digit in the free choices and adds their frequencies to the correct mask

• Iterate over i from start to end
  • Decrement a[i]
  • Iterate over j from 0 to (size of mask - 1)
    • Declare integer array needed
    • Declare and initialize integer sum = 0
    • Declare and initialize boolean ok = true
    • Iterate over k from 0 to 9
      • If the kth bit is set in j
        • If a[k] < 0
          • ok = false
          • Break
        • Increment sum by a[k]
        • If sum > digitsAvailable
          • ok = false
          • Break
        • Append a[k] to needed
    • If not ok
      • Continue
    • Increment mask[j] by count(digitsAvailable, needed)
  • Increment a[i]

leadingZeros function

Function arguments - integer array ‘mask’, integer array of ‘digits’, given integer array ‘a’

Takes care of the cases, which can have counting of leading zeros.

• Declare and initialize integer nd = size of digits
• Iterate over i from 1 to nd-1
  • fillAnyDigits(mask, a, 1, 9, nd-i-1)

magical0ToN function

Function arguments - integer ‘n’, given integer array ‘a’

Returns number of magical numbers in the range of [0,n]

• Declare integer array mask of size 2^10
• Declare and initialize integer nCpy = n
• Declare integer array digits
• While nCpy > 0
  • Append (nCpy % 10) to digits
  • Divide nCpy by 10
• Reverse digits array
• leadingZeros(mask, digits, a)
• Declare and initialize integer nd = size of digits array
• Iterate over i from 0 to nd-1
  • fillAnyDigits(mask, a, (1 if i == 0 and 0 otherwise), (digits[i] if i == nd - 1 and digits[i]-1 otherwise), nd-i-1)
  • Decrement a[digits[i]]
• Declare and initilaize integer ans = 0
• Iterate over i from 1 to 2^10 - 1
  • Declare and initialize integer seBits = no. of bits set in the binary representation of i
  • If setBits is odd
    • Add mask[i] to ans
  • Otherwise, if setBits are even
    • Subtract mask[i] from ans
• Return ans

Given Function

• Return ((r-l+1) - (magical0toN(r, a) - magical0toN(l-1, a)))