## Algorithm

Problem Name: 1012. Numbers With Repeated Digits

Given an integer `n`, return the number of positive integers in the range `[1, n]` that have at least one repeated digit.

Example 1:

```Input: n = 20
Output: 1
Explanation: The only positive number (<= 20) with at least 1 repeated digit is 11.
```

Example 2:

```Input: n = 100
Output: 10
Explanation: The positive numbers (<= 100) with atleast 1 repeated digit are 11, 22, 33, 44, 55, 66, 77, 88, 99, and 100.
```

Example 3:

```Input: n = 1000
Output: 262
```

Constraints:

• `1 <= n <= 109`

## Code Examples

### #1 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const numDupDigitsAtMostN = function(N) {
const L = [];
for (let x = N + 1; x > 0; x = Math.floor(x / 10)) L.unshift(x % 10);

// Count the number with digits  <  N
let res = 0,
n = L.length;
for (let i = 1; i  <  n; ++i) res += 9 * A(9, i - 1);

const seen = new Set();
for (let i = 0; i  <  n; ++i) {
for (let j = i > 0 ? 0 : 1; j  <  L[i]; ++j)
if (!seen.has(j)) res += A(9 - i, n - i - 1);
if (seen.has(L[i])) break;
}
return N - res;
};

function A(m, n) {
return n === 0 ? 1 : A(m, n - 1) * (m - n + 1);
}
``````
Copy The Code &

Input

cmd
n = 20

Output

cmd
1

### #2 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution(object):
def numDupDigitsAtMostN(self, N):
"""
:type N: int
:rtype: int
"""
# given number n, see whether n has repeated number
def has_repeated(n):
str_n = str(n)
return len(set(str_n)) != len(str_n)

def permutation(n, k):
prod = 1
for i in range(k):
prod *= (n-i)
return prod

# calculate number of non-repeated n-digit numbers
# note: the n-digit number can't start with 0
# i.e: n_digit_no_repeat(2) calculates the non-repeated
#   numbers in range [10, 99] (inclusive)
def n_digit_no_repeat(n):
if n == 1:
return 9
else:
return  9 * permutation(9, n-1)

N_str = str(N)
n_digit = len(N_str)
digits = list(map(int, N_str))
result = N - 1
prefix = 0
for i in range(1, n_digit):
result -= n_digit_no_repeat(i)
for i in range(n_digit):
# when we fix the most significant digit, it
# can't be zero
start = 0 if i else 1
for j in range(start, digits[i]):
if has_repeated(prefix * 10 + j):
continue
result -= permutation(9 - i, n_digit-1-i)
prefix = prefix*10 + digits[i]
return result + has_repeated(N)
``````
Copy The Code &

Input

cmd
n = 20

Output

cmd
1