No Repeated Digits

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
0 upvote
Asked in companies
TCSTCS

Problem statement

Elon is a kid who just started learning about numbers, but he always gets afraid when he sees a number with repeated digits, as it becomes hard for him to remember it as it has the same digits repeating again.

So his teacher, knowing of his fear, gave him ‘N’ tasks to cheer him up, for each task Elon have to count the numbers that have no repeated digits in a given range of [‘L’, ‘R’]. The tasks are given by a 2d array ‘TASKS’.

But Elon is again afraid that while counting he may encounter a number with repeated digits, being his friend he asked you to help him. Can you help Elon to find the count of numbers having no repeated digits in the given range for each task?.

NOTE: Both ‘L’ and ‘R’ are included in the range.

Example : 
Input: ‘N’ = 1, ‘TASKS = [ [1, 20] ]

Output: 19
For the first task, the given range consists of 20 numbers present out of which ‘11’ is the only number that has repeated occurrences of ‘1’ in its decimal representation.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line will contain the integer 'T', the number of test cases.

The first line of each test case contains one integer ‘N’ denoting the length of the array.

The next ‘N’ lines of each test case contain 2 integers, [ ‘L’, ‘R’ ] denoting the range (‘L’, ‘R’).
Output format : 
For each test case, print an array consisting of the count of numbers in the given range which has no repeated digits in it for each task.
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’ <= 1000
1 <= ‘L’ <= ‘R’ <= 10^5
Time Limit: 1 sec
Sample Input 1 :
1
2
1 20
100 110
Sample Output 1 :
19 8
Explanation Of Sample Input 1 :
For the first test case,
For the first task, the given range consists of 20 numbers present out of which ‘11’ is the only number that has repeated occurrences of ‘1’ in its decimal representation.
For the second task, the given range consists of 11 numbers present out of which ‘100’, ‘101’, and ‘110’ are the numbers that have repeated occurrences of ‘1’ in its decimal representation.

Hence, the output will be: 19, 8.
Sample Input 2 :
2
2
11 11
1 100
3
10 11
11 12
12 13
Sample Output 2 :
0 90
1 1 2
Hint

Can we iterate on the whole range one by one?.

Approaches (2)
Brute Force Approach

The idea of this approach is to count all the number that has no repeated digits in the range ‘[L, R]’ by iterating on them one by one for each task.

We can create a function that when given a number returns ‘true’ if the number has no repeated digits otherwise ‘false’.

Then we iterate from ‘L’ to ‘R’ and call the function, if it returns true we increment the answer and we will do it for all the tasks and finally print the result.

 

Algorithm:

// The function will return true if the given number ‘X’ has repeated digits or not.

Boolean haveRepeatedDigits(X)

  • Create an unordered set with the name of ‘digits’.
  • Run a while loop until ‘X’ don’t become ’0’.
    • Initialize a variable named ‘digit’ with the value of the remainder of ‘X’ divided by ‘10’.
    • If ‘digit’ is present in the unordered set ‘digits’
      • Return ‘true’
    • Else
      • Insert ‘digit’ into ‘digits’.
    • Divide ‘X’ by ‘10’.
  • Return ‘false’.


 

// The function will return the count of numbers in the range ‘[L, R]’ that has no repeated digits for each task.

Int noRepeatedDigits(vecor<int>& tasks):

  • Declare an array named ‘ANS’ which will store the final result of all the tasks.
  • Iterate over the ‘TASKS’, for ‘i’ = 0…’N’-1:
    • Initialize a variable named ‘noRepeatedDigit’ with the value of zero.
    • Run a for loop from ‘L’ to ‘R’ with a variable named ‘num’
      • If ‘haveRepeatedDigits(num)’ returns ‘false’
        • Increment ‘noRepeatedDigit’ by one.
    • Append ‘noRepeatedDigit’ into the ‘ANS’ array.
  • Return the ‘ANS’ array.
Time Complexity

O(N*maxR*K), Where ‘maxR’ is the maximum value of ‘R’ over all the tasks, ‘N’ is the number of tasks and ‘K’ is the maximum number of digits in the decimal representation of any number.

As we are running a for loop from ‘L’ to ‘R’ and in each iteration, we call the ‘haveRepeatedDigits’ function which in the worst case can need ‘K’ iterations in the case of a ‘K’-digit number, the whole process is repeated for each task, hence the time complexity will be O(N*maxR*K).

Space Complexity

O(K), Where ‘K’ is the numbe of digits.


As we are using only variable ‘noRepeatedDigit’ and an unordered set ‘digits’ which in the worst case have a size of six, but let us assume that the digit can be utmost ‘K’ then the space complexity will be O(‘K’), and the space taken by the ‘ANS’ array can be ignored.

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