Count Integers

In this approach, We will simply count invalid numbers( numbers with no repeated digits ) and subtract them from the number ‘N’ and get the count of numbers with repeated digits.

We can use bit masking to solve this problem.  Let ‘bitmask’ be any integer. In the binary representation of ‘bitmasking’, if the bit at position ‘2^pos’ is ‘1’ then it denotes that the integer contains a digit = pos.

Now if the bitwise ‘and’ operation of ‘bitmask’ with  ‘2^d’ is greater than ‘0’, then it denotes that digit ‘d’ is present in the number.

For Example - If a number is ‘13’ then its bitmasking number will be‘10000010’.(2nd,8th bit = 1). Now bitwise and of ‘10000010’ with 2^1 > 0, which denotes digit 1 is present in number.

We will recursively generate all the invalid integers between 1 and N and keep a count of them.

Algorithm

• Let ‘countInvalid’ be a recursive function that takes an integer ‘cur’ initially ‘0’ denoting the current number, an integer ‘bitmask’, integer ‘N’, and an integer ‘count’ initially ‘0’ denoting the count of numbers with non-repeating digits.
• If cur > N, i.e current number becomes greater than ‘N’, return. Otherwise, increment ‘count’ by ‘1’.
• Run a loop i:0 to 9 to add all digits to the current number.
• If ‘bitmask’ is ‘0’ and ‘digit’ is ‘0’, continue with the next digit.
• If bitwise and of ‘bitmask’ and ‘2^i’ is greater than 0, then continue with the next digit. It denotes that the digit ‘i’ is present in the current number, so no need to add digit ‘i’ to ‘cur’.
• Recursively call the function for cur = cur*10 + i and bitmask = bitwise OR of ‘bitmask’ and 2^i.

Now, ‘count’ will store the count of integers with non-repeating digits(including 0). So N - count + 1 will give the required answer.

The basic approach that we can use is to reverse the question and instead of counting the numbers with repeated digits, we will simply count numbers with no repeated digits. And using that count, we can subtract it from the number and get the count of numbers with repeated digits.

• ans = N - count, where “ans” is the count of numbers that have repeated digits, N is the given number and “count” is the count of numbers with no repeated digits.
• To count the numbers with no repeated digits, we will use the permutations formula.
• Permutation formula: N! / (N - R)!, where N is the number and R is the digits taken at a time.

We will use the permutations formula as it gives us the permutations of unique numbers. 

We will do this by varying the digits of the given number and counting the invalid numbers(numbers that have no repeated digits).

Let us understand this approach with the help of an example: 

Let N = 450, we have 3 digits in the given number. 

To start with we will first find the count of invalid numbers in the range (1 - 99).

There are no numbers of length 1 that can have any repeated digits, so simply add 9 to our count. 

Now to get invalid numbers of length 2, we have one digit that we can change. Like if the number is 1X, then X can be varied, 2Y, Y can be varied, and so on. 

Now for ‘X’ we have 9 choices ( as we can not use ‘1’ to make number non-repeated).

Using our permutation formula for this, we have permutation(9, 1), where 9 is invalid numbers and 1 is the valid number. For the complete range of numbers with length two, we have, (9 + (permutation(9, 1) * 9)), which gives us 81 invalid numbers. Adding this into our previous count, we have 81 + 9 = 90 invalid numbers in the range of 1 - 99.

Similarly, we move on to count invalid numbers in the range 100-451(to ensure we have N also counted in the range). We do this by varying each of the digits of the numbers and keeping a count.

4XX -> permutation(9-0, 4-0-1) = permutation(9, 3)

X5X -> permutation(9-1, 4-1-1) = permutation(8, 2)

XX1 -> permutation(9-2, 4-2-1) = permutation(7, 1)

We use these permutations to count all the invalid numbers, which in this case will add up to: 339, and hence count of numbers with repeating digits will be :

450 - 339 = 111.

Algorithm:

• Initialize “invalidCount” with value = 0, which will store the count of invalid numbers.
• Initialize “length” that will store the number of digits, given number has.
• To start with we calculate all the valid numbers up to (10 ^ (length - 1)), for example for the given number 450, we will count invalid numbers between 1 and 99.
• Next, for each digit calculate possible invalid permutations that are available up until that digit.
  • Initialise “digits” with value = 0
  • Get the left-most digit of the number, store it in another variable let’s say “digit”
  • Count up to that digit, note that if it is the first digit, do not include 0
  • Also, if we have the same digit on the left previously, then do not include it this time. For example, If our number is 450, then skip the range 440-449. As it had been already counted in the previous iteration
  • Similarly, if we end up finding a digit we’ve already searched then simply break out of the iteration.
• Finally return N - “invalidCount”, which will be the count of numbers with repeated digits.