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