ARJN - Editorial

,
1

PROBLEM LINK

Practice

Author: Arjun Bharat
Editorialist: Kairav Shah

DIFFICULTY

Medium

PREREQUISITES

Basic Dynamic Programming, Permutation and Combinations

PROBLEM

Given 2 numbers a and b, find the number of integers in the range [a,b] such that they have at least one repeated digit.

EXPLANATION

The simplest brute force solution would be as follows:

  • Set answer as 0.
  • for(each number x in the range [a,b]):
    • extract each digit of the number x.
  • if any digit occurs more than once, increment the answer and move on to the next number.
  • print the answer.

A C++ code for this can be found here

However, the program constraints specify that a and b may be anywhere between 1 and INT_MAX(2,147,483,647).

Thus, this approach fails from an efficiency standpoint and exceeds the time limit.

Optimal Solution:
We resort to permutations to solve this problem. Observe that any approach involving generating the numbers themselves doesn’t work for the same reason as mentioned earlier - efficiency is quite poor.

Notation: P(c,d) denotes the number of ways to permute c objects among d spaces, when relative ordering matters.

cPd = c! / (c-d)! (if c >= d,d >= 0)
(If c < d, cPd is taken to be 0)

Let’s say that for a given number x, we want to calculate the number of integers less than or equal to x that have the said property. So define f(x) = number of integers less than or equal to x that have at least one repeated digit.

Then, answer = f(b) - f(a-1) (which gives us all the integers in the range [a,b] having the property)

We calculate f(x) as:

f(x) = (total number of +ve integers <= x (this equals x itself!) - (total number of +ve integers <= x that have NO repeated digit)
It is clear that this holds by mutual exclusivity.

To understand how we compute the value of f(x), let’s take an example:

  • Let’s say x = 324.
  • We want to count the number of integers <= 324 having NO repeated digits.
  • Suppose we change the hundreds place. To get a number <= 324, we can use only the digits {0,1,2} in the hundred’s place and any other unused digits in the tens and one’s place.
  • If any one of {1,2} is used in the hundreds place, we can use 9 other digits in the remaining 2 places while ensuring no repetition.
  • Thus, number of numbers possible in Case 1 is: 3 * P(9,2) = 2 * 72 = 144. (Not correct!)

However, we have to keep in mind that when 0 is used as the most significant digit of the number, it can be used once more in the remaining places since leading zeroes are not part of decimal representation. Thus with this portion, we have to be extra cautious while counting.

We want to count the total number of numbers of the form 0XX.(X can be any digit). Thus to do so, we traverse from left to right and sequentially increase the number of leading zeroes, from 1 to 3. This is done as follows:

  • Case i: numbers of the form 0XY: If we set X to be 0, we have a separate case to deal with. So assume X != 0.

    • Then, the number of such numbers = (Permutations of {0,1,…9} among 2 places) - (Permutations of the form 00Y, Y is one of {1,2,…9})
      = P(10,2) - P(9,1) = 90 - 9 = 81.

  • Case ii: numbers of the form 00Y: Here we have 9 choices for the units place(because 0 being used again gives us the number zero itself, which cannot be counted as it has no repeated digit.) Thus, 9 numbers in this case.

    • Total: 81 + 9 = 90 when the leading digit of the number is 0.

  • Therefore, total from Case 1 is 144 + 90 = 234.

  • Let us set the hundreds digit as 3 (which was not taken in Case 1, and this is the upper bound as well). To get a number <= 324, we can set the tens digit to be {0,1} and the unit’s digit to be any one of the remaining 8 digits(note that we cannot use 3 since it has already appeared at the hundred’s place). So, number of numbers in Case 2 is: 2 * P(8,1) = 16.

  • We set hundreds digit as 3, and ten’s digit as 2(which was not considered in Cases 1 and 2, and are the corresponding maximum values). Now the units digit can be any one of {0,1} only(2 and 3 will be considered initially since they are < 4, however they cannot be used as they have appeared already). Number of numbers in case 3 = 2.

  • So far we have considered all numbers < 324 in the above cases (why this is so should be fairly obvious). 324 itself has no repeated digits and thus is counted as well. Total count: 234 + 16 + 2 + 1 = 253.

  • Therefore, Number of numbers <= x having NO repeated digits = 253.

Therefore f(324) = 324 - 253 = 71.

Generic idea for an N digit number:

  1. Traverse the number from the most significant to the least significant digit.
  2. If we are the ith digit (assuming 1st digit is the most significant and so on):
    a) Consider the value of the digit, let it be X.
    b) Now the digits that can appear at this place of the number (retaining all digits at previous positions of the number to be the same (refer example)) will be {0,1,2,…X-1}.
    c) The set of digits that can appear in the places ahead of the ith position will be: S = {0,1,2,… 9} - {X} - {all digits that have been used in the positions 1,2,…i-1}.
    d) Therefore, number of numbers having no repeated digits in this case will be = X * P(cardinality of S,N-i).
  3. Add the answers to each case as computed earlier. Call this value SUM.
  4. Thus, f(N) = N - SUM.
  5. Then, answer to each test case = f(b) - f(a-1).

COMPLEXITY ANALYSIS

Complexity: O(T * log(INT_MAX)), since each test case is solved in O(number of digits) that is O(log(INT_MAX)) in the worst case.

The C++ code for the following is available here