Count Integers

Moderate
0/80
Average time to solve is 35m
1 upvote
Asked in companies
AdobeIncedo Inc.

Problem statement

Given a positive integer ‘N’, you need to find the number of integers between 1 and N(both inclusive), that have at least one digit repeated.

For Example: 
If N = 12, then only ‘11’ has repeated digits. Therefore the number of integers between 1 and 12 that have at least one digit repeated = 1.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains a single integer ‘T’, denoting the number of test cases.

The first line of each test case contains a single integer denoting ‘N’.
Output Format: 
For each test case, print a single line containing a single integer denoting the number of integers between 1 and ‘N’ having at least one repeated digit.

The output of each test case will be printed in a separate line.
Note: 
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= N <= 10 ^ 9

Where ‘T’ is the number of test cases, and ‘N’ is the given integer.

Time limit: 1 sec.
Sample Input 1:
2
58
140
Sample Output 1:
5
25
Explanation Of Sample Input 1:
Test Case 1: Integers 11, 22, 33, 44,55 lie between 1 and 58 having at least one repeated digit. 

Test Case 2: Integers between 1 and 140 having at least one repeating digit are 11, 22, 33, 44, 55, 66, 77, 88, 99, 100, 101, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 121, 122, 131, 133.
Sample Input 2:
2
208
190
Sample Output 2:
39
35
Hint

Try to generate every integer with non-repeating digits.

Approaches (2)
Recursion and Bit Masking

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.

Time Complexity

O(N), where ‘N’ is the given number.

 

We are generating every integer with non-repeating digits. So the time complexity is O(N).

Space Complexity

O(N), where ‘N’ is the given number.

 

We are taking a ‘bitmask’ integer for every number, making the space complexity O(N).

Code Solution
(100% EXP penalty)
Count Integers
Full screen
Console