Задача: 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 {
public:
    int numDupDigitsAtMostN(int n) {
        return n - countUniqueDigitNumbers(n);
    }

private:
    int countUniqueDigitNumbers(int x) {
        string s = to_string(x);
        int n = s.size();
        int res = 0;
        for (int i = 1; i < n; ++i) {
            res += 9 * permutation(9, i - 1);
        }
        unordered_set<int> used;
        for (int i = 0; i < n; ++i) {
            for (int j = (i == 0 ? 1 : 0); j < s[i] - '0'; ++j) {
                if (used.find(j) == used.end()) {
                    res += permutation(9 - i, n - i - 1);
                }
            }
            if (used.find(s[i] - '0') != used.end()) {
                break;
            }
            used.insert(s[i] - '0');
        }
        if (used.size() == n) {
            res += 1;
        }
        return res;
    }

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

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