# Total numbers with no repeated digits in a range

Given a range 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
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

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++

 `// C++ implementation of brute ` `// force solution. ` `#include ` `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; ` `} ` ` `  `// This code is contributed by ` `// Sanjit_Prasad `

## Java

 `// Java implementation of brute  ` `// force solution.  ` `import` `java.util.LinkedHashSet; ` ` `  `class` `GFG ` `{ ` `// Function to check if the given  ` `// number has repeated digit or not  ` `static` `int` `repeated_digit(``int` `n)  ` `{ ` `    ``LinkedHashSet s = ``new` `LinkedHashSet<>(); ` ` `  `    ``// Traversing through each digit  ` `    ``while` `(n != ``0``)  ` `    ``{ ` `        ``int` `d = n % ``10``; ` ` `  `        ``// if the digit is present  ` `        ``// more than once in the  ` `        ``// number  ` `        ``if` `(s.contains(d)) ` `        ``{ ` `            ``// return 0 if the number  ` `            ``// has repeated digit  ` `            ``return` `0``; ` `        ``} ` `        ``s.add(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  ` `static` `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  ` `public` `static` `void` `main(String[] args)  ` `{ ` `    ``int` `L = ``1``, R = ``100``; ` `     `  `    ``// Calling the calculate  ` `    ``System.out.println(calculate(L, R)); ` `} ` `} ` ` `  `// This code is contributed by RAJPUT-JI `

## Python3

 `# Python implementation of brute  ` `# force solution. ` ` `  `# Function to check if the given  ` `# number has repeated digit or not  ` `def` `repeated_digit(n): ` `    ``a ``=` `[] ` `     `  `    ``# Traversing through each digit ` `    ``while` `n !``=` `0``: ` `        ``d ``=` `n``%``10` `         `  `        ``# if the digit is present ` `        ``# more than once in the ` `        ``# number ` `        ``if` `d ``in` `a: ` `             `  `            ``# return 0 if the number ` `            ``# has repeated digit ` `            ``return` `0` `        ``a.append(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 ` `def` `calculate(L,R): ` `    ``answer ``=` `0` `     `  `    ``# Traversing through the range ` `    ``for` `i ``in` `range``(L,R``+``1``): ` `         `  `        ``# Add 1 to the answer if i has ` `        ``# no repeated digit else 0 ` `        ``answer ``=` `answer ``+` `repeated_digit(i) ` `     `  `    ``# return answer ` `    ``return` `answer ` `     `  `# Driver's Code  ` `L``=``1` `R``=``100` ` `  `# Calling the calculate ` `print``(calculate(L, R)) `

## C#

 `// C# implementation of brute  ` `// force solution.  ` `using` `System;  ` `using` `System.Collections.Generic;  ` ` `  `class` `GFG  ` `{ ` ` `  `// Function to check if the given  ` `// number has repeated digit or not  ` `static` `int` `repeated_digit(``int` `n) ` `{ ` `    ``var` `s = ``new` `HashSet<``int``>(); ` ` `  `    ``// Traversing through each digit  ` `    ``while` `(n != 0) ` `    ``{ ` `        ``int` `d = n % 10; ` ` `  `        ``// if the digit is present  ` `        ``// more than once in the  ` `        ``// number  ` `        ``if` `(s.Contains(d))  ` `        ``{ ` `            ``// return 0 if the number  ` `            ``// has repeated digit  ` `            ``return` `0; ` `        ``} ` `        ``s.Add(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  ` `static` `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  ` `public` `static` `void` `Main(String[] args) ` `{ ` `    ``int` `L = 1, R = 100; ` `     `  `    ``// Calling the calculate  ` `    ``Console.WriteLine(calculate(L, R)); ` `} ` `} ` ` `  `// This code is contributed by RAJPUT-JI `

## PHP

 ` 0) ` `    ``{ ` `        ``\$d` `= ``\$n` `% 10; ` `         `  `        ``// if the digit is present ` `        ``// more than once in the ` `        ``// number ` `        ``if` `(``\$a``[``\$d``] > 0) ` `        ``{ ` `            ``// return 0 if the number ` `            ``// has repeated digit ` `            ``return` `0; ` `        ``} ` `        ``\$a``[``\$d``]++; ` `        ``\$n` `= (int)(``\$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 ` `function` `calculate(``\$L``, ``\$R``) ` `{ ` `    ``\$answer` `= 0; ` `     `  `    ``// Traversing through ` `    ``// the range ` `    ``for``(``\$i` `= ``\$L``; ``\$i` `<= ``\$R``; ``\$i``++) ` `    ``{ ` `         `  `        ``// Add 1 to the answer if  ` `        ``// i has no repeated digit ` `        ``// else 0 ` `        ``\$answer` `+= repeated_digit(``\$i``); ` `    ``} ` `     `  `    ``// return answer ` `    ``return` `\$answer``; ` `}  ` ` `  `// Driver Code  ` `\$L` `= 1; ` `\$R` `= 100; ` ` `  `// Calling the calculate ` `echo` `calculate(``\$L``, ``\$R``); ` ` `  `// This code is contributed by mits ` `?> `

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. = Total number with no repeated digit less than or equal to 1.

Therefore each query can be solved in O(1) time. Below is the implementation of above idea.

## C++

 `// C++ implementation of above idea  ` `#include   ` ` `  `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; ` `} ` ` `  `// This code is contributed by Rituraj Jain `

## Python3

 `# Python implementation of  ` `# above idea ` ` `  `# Prefix Array ` `Prefix ``=` `[``0``] ` ` `  `# Function to check if  ` `# the given number has  ` `# repeated digit or not  ` `def` `repeated_digit(n): ` `    ``a ``=` `[] ` `     `  `    ``# Traversing through each digit ` `    ``while` `n !``=` `0``: ` `        ``d ``=` `n``%``10` `         `  `        ``# if the digit is present ` `        ``# more than once in the ` `        ``# number ` `        ``if` `d ``in` `a: ` `             `  `            ``# return 0 if the number ` `            ``# has repeated digit ` `            ``return` `0` `        ``a.append(d) ` `        ``n ``=` `n``/``/``10` `     `  `    ``# return 1 if the number has no ` `    ``# repeated digit ` `    ``return` `1` ` `  `# Function to pre calculate ` `# the Prefix array ` `def` `pre_calculation(``MAX``): ` `     `  `    ``# To use to global Prefix array ` `    ``global` `Prefix ` `    ``Prefix.append(repeated_digit(``1``)) ` `     `  `    ``# Traversing through the numbers ` `    ``# from 2 to MAX ` `    ``for` `i ``in` `range``(``2``,``MAX``+``1``): ` `         `  `        ``# Generating the Prefix array  ` `        ``Prefix.append( repeated_digit(i) ``+` `                       ``Prefix[i``-``1``] ) ` ` `  `# Calclute Function ` `def` `calculate(L,R): ` `     `  `    ``# Answer ` `    ``return` `Prefix[R]``-``Prefix[L``-``1``] ` ` `  ` `  `# Driver Code ` ` `  `# Maximum  ` `MAX` `=` `1000` ` `  `# Pre-calculating the Prefix array. ` `pre_calculation(``MAX``) ` ` `  `# Range ` `L``=``1` `R``=``100` ` `  `# Calling the calculate function ` `# to find the total number of number ` `# which has no repeated digit ` `print``(calculate(L, R)) `

Output:

```90
```

This article is attributed to GeeksforGeeks.org

code

load comments