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

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

Пример:

Input: n = 20
Output: 1

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

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

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

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

😎 Решение:

public class Solution {
    public int numDupDigitsAtMostN(int n) {
        return n - countUniqueDigitNumbers(n);
    }

    private int countUniqueDigitNumbers(int x) {
        String s = Integer.toString(x);
        int n = s.length();
        int res = 0;

        for (int i = 1; i < n; i++) {
            res += 9 * permutation(9, i - 1);
        }

        Set<Integer> used = new HashSet<>();
        for (int i = 0; i < n; i++) {
            for (int j = (i == 0 ? 1 : 0); j < s.charAt(i) - '0'; j++) {
                if (!used.contains(j)) {
                    res += permutation(9 - i, n - i - 1);
                }
            }
            if (used.contains(s.charAt(i) - '0')) {
                break;
            }
            used.add(s.charAt(i) - '0');
        }

        if (used.size() == n) {
            res++;
        }

        return res;
    }

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

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