Hello Everyone,
Given a range L, R find total such numbers in the given range such that they have no repeated digits.
For example:
12 has no repeated digit.
22 has repeated digit.
102, 194 and 213 have no repeated digit.
212, 171 and 4004 have repeated digits.
Examples:
Input : 10 12 Output : 2 Explanation : In the given range 10 and 12 have no repeated digit where as 11 has repeated digit. Input : 1 100 Output : 90
Brute Force
We will traverse through each element in the given range and count the number of digits which do not have repeated digits.
// C++ implementation of brute
// force solution.
#include <bits/stdc++.h>
using
namespace
std;
// Function to check if the given
// number has repeated digit or not
int
repeated_digit(
int
n)
{
unordered_set<
int
> s;
// Traversing through each digit
while
(n != 0)
{
int
d = n % 10;
// if the digit is present
// more than once in the
// number
if
(s.find(d) != s.end())
{
// return 0 if the number
// has repeated digit
return
0;
}
s.insert(d);
n = n / 10;
}
// return 1 if the number has
// no repeated digit
return
1;
}
// Function to find total number
// in the given range which has
// no repeated digit
int
calculate(
int
L,
int
R)
{
int
answer = 0;
// Traversing through the range
for
(
int
i = L; i < R + 1; ++i)
{
// Add 1 to the answer if i has
// no repeated digit else 0
answer = answer + repeated_digit(i);
}
return
answer ;
}
// Driver Code
int
main()
{
int
L = 1, R = 100;
// Calling the calculate
cout << calculate(L, R);
return
0;
}
Output:
90
This method will answer each query in O( N ) time.
Efficient Approach
We will calculate a prefix array of the numbers which have no repeated digit.
Therefore each query can be solved in O(1) time.
Below is the implementation of above idea.
// C++ implementation of above idea
#include <bits/stdc++.h>
using
namespace
std;
// Maximum
int
MAX = 1000;
// Prefix Array
vector<
int
> Prefix = {0};
// Function to check if the given
// number has repeated digit or not
int
repeated_digit(
int
n)
{
unordered_set<
int
> a;
int
d;
// Traversing through each digit
while
(n != 0)
{
d = n % 10;
// if the digit is present
// more than once in the
// number
if
(a.find(d) != a.end())
// return 0 if the number
// has repeated digit
return
0;
a.insert(d);
n = n / 10;
}
// return 1 if the number has no
// repeated digit
return
1;
}
// Function to pre calculate
// the Prefix array
void
pre_calculation(
int
MAX)
{
Prefix.push_back(repeated_digit(1));
// Traversing through the numbers
// from 2 to MAX
for
(
int
i = 2; i < MAX + 1; i++)
// Generating the Prefix array
Prefix.push_back(repeated_digit(i) + Prefix[i-1]);
}
// Calclute Function
int
calculate(
int
L,
int
R)
{
// Answer
return
Prefix[R] - Prefix[L-1];
}
// Driver code
int
main()
{
int
L = 1, R = 100;
// Pre-calculating the Prefix array.
pre_calculation(MAX);
// Calling the calculate function
// to find the total number of number
// which has no repeated digit
cout << calculate(L, R) << endl;
return
0;
}
Output:
90