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;
seen.add(L[i]);
}
return N - res;
};
function A(m, n) {
return n === 0 ? 1 : A(m, n - 1) * (m - n + 1);
}
Input
n = 20
Output
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)
Input
n = 20
Output
1