# 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