Total numbers with no repeated digits in a range

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