Last Updated: 17 Jun, 2022
No Repeated Digits
Moderate
Asked in companies
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.
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
Approaches
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.
- If ‘haveRepeatedDigits(num)’ returns ‘false’
- Append ‘noRepeatedDigit’ into the ‘ANS’ array.
- Return the ‘ANS’ array.
The idea for this approach is to once precalculate the numbers that have no repeated digits up to the maximum possible value of ‘R’ and store them in some array.
After precalculating we can use the below idea to find the answer for any given range ‘L’ to ‘R’ in constant time.
The idea is to get the count of all the numbers that have no repeated digits in the range ‘[1, R]’ using the precalculation value stored in the array and subtract the count of numbers that has no repeated digits in the range ‘[1, L-1]’.
It is easy to observe how this always works, as it first includes all the numbers having no repeated digits from ‘1’ to ‘R’ and then excludes all the numbers having no repeated digits, that are not in the range ‘L’ to ‘R’ i.e. the numbers that have no repeated digits in the range ‘1’ to ‘L - 1’.
The things we need to take care of while implementing this solution are,
- Zero is not considered in the precalculation range.
- To take care of the case when ‘L’ = 1, in this case, we just need to return the count for the range ‘[1, R]’ without any subtraction.
- Do the precalculation once for 1 to the maximum value of ‘R’ and then use its value for all the following tasks.
Algorithm:
// The function will return 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 zero.
- 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 does the precalculation and returns the ‘precalculatedCount’ array.
vector<int> preCalculate(maxR)
- Declare an array ‘precalculatedCount’ of size ‘maxR + 1’.
- Initialize a variable named ‘count’ with the value of zero.
- Run a for loop from ‘1’ to ‘maxR’ with a variable named ‘num’.
- If ‘haveRepeatedDigits(num)’ returns ‘false’
- Increment ‘count’ by one.
- Assign ‘precalculatedCount[num]’ the value of ‘count’.
- If ‘haveRepeatedDigits(num)’ returns ‘false’
- Return the ‘precalculatedCount’ array.
// The function will return the count of numbers in the range ‘[L, R]’ that has no repeated digits for each task.
Int noRepeatedDigits(vector<int>& tasks)
- Initialize a variable named ‘maxR’ with the value of maximum ‘R’ value present in the ‘TASKS’ array.
- Call ‘preCalculate(maxR)’ and assign the array returned by the function to a new array ‘precalculatedCount’.
- 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 ‘precalculatedCount[R]’.
- If ‘L != 1’
- Subtract the value of ‘precalculatedCount[L-1]’ from ‘noRepeatedDigit’.
- Append ‘noRepeatedDigit’ into the ‘ANS’ array.
- Return the ‘ANS’ array.