1012. Numbers With Repeated Digits

public class Solution {
    public int NumDupDigitsAtMostN(int n) {
        return n - CountUniqueDigitNumbers(n);
    }
    private int CountUniqueDigitNumbers(int x) {
        var s = x.ToString();
        var n = s.Length;
        var res = 0;
        for (var i = 1; i < n; i++) {
            res += 9 * Permutation(9, i - 1);
        }
        var used = new HashSet<int>();
        for (var i = 0; i < n; i++) {
            for (var j = (i == 0 ? 1 : 0); j < s[i] - '0'; j++) {
                if (!used.Contains(j)) {
                    res += Permutation(9 - i, n - i - 1);
                }
            }
            if (used.Contains(s[i] - '0')) {
                break;
            }
            used.Add(s[i] - '0');
        }
        if (used.Count == n) {
            res++;
        }
        return res;
    }
    private int Permutation(int m, int n) {
        return n == 0 ? 1 : Permutation(m, n - 1) * (m - n + 1);
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int NumDupDigitsAtMostN(int n) {
        return n - CountUniqueDigitNumbers(n);
    }
    private int CountUniqueDigitNumbers(int x) {
        var s = x.ToString();
        var n = s.size();
        var res = 0;
        for (var i = 1; i < n; i++) {
            res += 9 * Permutation(9, i - 1);
        }
        var used = new HashSet<int>();
        for (var i = 0; i < n; i++) {
            for (var j = (i == 0 ? 1 : 0); j < s[i] - '0'; j++) {
                if (!used.Contains(j)) {
                    res += Permutation(9 - i, n - i - 1);
                }
            }
            if (used.Contains(s[i] - '0')) {
                break;
            }
            used.push_back(s[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);
    }
}

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);
    }
}

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);
    }
}

func numDupDigitsAtMostN(n int) int {
    return n - countUniqueDigitNumbers(n)
}

func countUniqueDigitNumbers(x int) int {
    s := strconv.Itoa(x)
    n := len(s)
    res := 0

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

    used := make(map[int]bool)
    for i := 0; i < n; i++ {
        for j := 0; j < int(s[i]-'0'); j++ {
            if i == 0 && j == 0 {
                continue
            }
            if !used[j] {
                res += permutation(9-i, n-i-1)
            }
        }
        if used[int(s[i]-'0')] {
            break
        }
        used[int(s[i]-'0')] = true
    }

    if len(used) == n {
        res++
    }

    return res
}

func permutation(m, n int) int {
    if n == 0 {
        return 1
    }
    return permutation(m, n-1) * (m - n + 1)
}

Algorithm

Вычисление всех чисел с уникальными цифрами:

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

Вычисление всех чисел в диапазоне [1, n]:

Это значение равно n, поскольку это количество всех чисел от 1 до n включительно.

Вычисление результата:

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

😎