Сложность: hard
Задав целое число n, верните количество положительных целых чисел в диапазоне [1, n], у которых хотя бы одна цифра повторяется.
Пример:
Input: n = 20
Output: 1
👨💻 Алгоритм:
1⃣Вычисление всех чисел с уникальными цифрами:
Найдите количество чисел в диапазоне [1, n], у которых все цифры уникальны. Для этого используйте перебор всех чисел и проверку уникальности цифр.
2⃣Вычисление всех чисел в диапазоне [1, n]:
Это значение равно n, поскольку это количество всех чисел от 1 до n включительно.
3⃣Вычисление результата:
Вычтите количество чисел с уникальными цифрами из общего количества чисел, чтобы получить количество чисел с повторяющимися цифрами.
😎 Решение:
class Solution {
func numDupDigitsAtMostN(_ n: Int) -> Int {
func countUniqueDigitNumbers(_ x: Int) -> Int {
let s = String(x)
let n = s.count
var res = (1..<n).reduce(0) { $0 + 9 * permutation(9, $1 - 1) }
var used = Set<Int>()
for (i, c) in s.enumerated() {
for j in (i == 0 ? 1 : 0)..<Int(String(c))! {
if !used.contains(j) {
res += permutation(9 - i, n - i - 1)
}
}
if used.contains(Int(String(c))!) {
break
}
used.insert(Int(String(c))!)
}
return used.count == n ? res + 1 : res
}
func permutation(_ m: Int, _ n: Int) -> Int {
return n == 0 ? 1 : permutation(m, n - 1) * (m - n + 1)
}
return n - countUniqueDigitNumbers(n)
}
}Ставь 👍 и забирай 📚 Базу знаний