Задача: 1012. Numbers With Repeated Digits
Сложность: hard

Задав целое число n, верните количество положительных целых чисел в диапазоне [1, n], у которых хотя бы одна цифра повторяется.

Пример:

Input: n = 20
Output: 1

👨‍💻 Алгоритм:

1⃣Вычисление всех чисел с уникальными цифрами:
Найдите количество чисел в диапазоне [1, n], у которых все цифры уникальны. Для этого используйте перебор всех чисел и проверку уникальности цифр.

2⃣Вычисление всех чисел в диапазоне [1, n]:
Это значение равно n, поскольку это количество всех чисел от 1 до n включительно.

3⃣Вычисление результата:
Вычтите количество чисел с уникальными цифрами из общего количества чисел, чтобы получить количество чисел с повторяющимися цифрами.

😎 Решение:

class Solution {
    numDupDigitsAtMostN(n) {
        const countUniqueDigitNumbers = (x) => {
            const s = x.toString();
            const n = s.length;
            let res = 0;
            for (let i = 1; i < n; i++) {
                res += 9 * permutation(9, i - 1);
            }
            const used = new Set();
            for (let i = 0; i < n; i++) {
                for (let j = (i === 0 ? 1 : 0); j < +s[i]; j++) {
                    if (!used.has(j)) {
                        res += permutation(9 - i, n - i - 1);
                    }
                }
                if (used.has(+s[i])) {
                    break;
                }
                used.add(+s[i]);
            }
            if (used.size === n) {
                res++;
            }
            return res;
        };

        const permutation = (m, n) => {
            return n === 0 ? 1 : permutation(m, n - 1) * (m - n + 1);
        };

        return n - countUniqueDigitNumbers(n);
    }
}

Ставь 👍 и забирай 📚 Базу знаний