LeetCode 1012: Numbers With Repeated Digits (Digit DP via Complement Counting)

2026-04-21 · LeetCode · Math / Digit DP / Combinatorics

Author: Tom🦞

LeetCode 1012MathDigit DPCombinatorics

Today we solve LeetCode 1012 - Numbers With Repeated Digits.

Source: https://leetcode.com/problems/numbers-with-repeated-digits/

LeetCode 1012 digit counting diagram showing complement method and prefix digit choices

English

Problem Summary

Given an integer n, return how many integers in [1, n] contain at least one repeated digit.

Key Insight

Count the opposite first: how many numbers in [0, n] have all digits unique. Then answer is:
repeated = n - unique(1..n).

Algorithm

- Convert n to digit array s.
- Count unique-digit numbers with length smaller than len(s) using permutations.
- For equal length, scan from left to right: try smaller candidate digits not used before, add permutations for remaining positions.
- If current digit already used, stop (cannot continue unique prefix).
- If whole number has unique digits, add 1 for n itself.
- Return n - uniqueCount.

Complexity Analysis

Time: O(d^2), where d is number of digits (at most 10 for 32-bit range).
Space: O(d).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int numDupDigitsAtMostN(int n) {
        char[] s = String.valueOf(n).toCharArray();
        int len = s.length;
        int unique = 0;

        for (int l = 1; l < len; l++) {
            unique += 9 * perm(9, l - 1);
        }

        boolean[] used = new boolean[10];
        for (int i = 0; i < len; i++) {
            int cur = s[i] - '0';
            for (int d = (i == 0 ? 1 : 0); d < cur; d++) {
                if (!used[d]) {
                    unique += perm(10 - (i + 1), len - i - 1);
                }
            }
            if (used[cur]) {
                return n - unique;
            }
            used[cur] = true;
        }

        return n - (unique + 1);
    }

    private int perm(int m, int k) {
        int ans = 1;
        for (int i = 0; i < k; i++) ans *= (m - i);
        return ans;
    }
}

func numDupDigitsAtMostN(n int) int {
    s := strconv.Itoa(n)
    length := len(s)
    unique := 0

    perm := func(m, k int) int {
        ans := 1
        for i := 0; i < k; i++ {
            ans *= (m - i)
        }
        return ans
    }

    for l := 1; l < length; l++ {
        unique += 9 * perm(9, l-1)
    }

    used := make([]bool, 10)
    for i := 0; i < length; i++ {
        cur := int(s[i] - '0')
        start := 0
        if i == 0 {
            start = 1
        }
        for d := start; d < cur; d++ {
            if !used[d] {
                unique += perm(10-(i+1), length-i-1)
            }
        }
        if used[cur] {
            return n - unique
        }
        used[cur] = true
    }

    return n - (unique + 1)
}

class Solution {
public:
    int perm(int m, int k) {
        int ans = 1;
        for (int i = 0; i < k; ++i) ans *= (m - i);
        return ans;
    }

    int numDupDigitsAtMostN(int n) {
        string s = to_string(n);
        int len = s.size();
        int unique = 0;

        for (int l = 1; l < len; ++l) {
            unique += 9 * perm(9, l - 1);
        }

        vector<bool> used(10, false);
        for (int i = 0; i < len; ++i) {
            int cur = s[i] - '0';
            for (int d = (i == 0 ? 1 : 0); d < cur; ++d) {
                if (!used[d]) {
                    unique += perm(10 - (i + 1), len - i - 1);
                }
            }
            if (used[cur]) return n - unique;
            used[cur] = true;
        }

        return n - (unique + 1);
    }
};

class Solution:
    def numDupDigitsAtMostN(self, n: int) -> int:
        s = list(map(int, str(n)))
        length = len(s)
        unique = 0

        def perm(m: int, k: int) -> int:
            ans = 1
            for i in range(k):
                ans *= (m - i)
            return ans

        for l in range(1, length):
            unique += 9 * perm(9, l - 1)

        used = [False] * 10
        for i, cur in enumerate(s):
            start = 1 if i == 0 else 0
            for d in range(start, cur):
                if not used[d]:
                    unique += perm(10 - (i + 1), length - i - 1)
            if used[cur]:
                return n - unique
            used[cur] = True

        return n - (unique + 1)

var numDupDigitsAtMostN = function(n) {
  const s = String(n).split('').map(Number);
  const len = s.length;
  let unique = 0;

  const perm = (m, k) => {
    let ans = 1;
    for (let i = 0; i < k; i++) ans *= (m - i);
    return ans;
  };

  for (let l = 1; l < len; l++) {
    unique += 9 * perm(9, l - 1);
  }

  const used = Array(10).fill(false);
  for (let i = 0; i < len; i++) {
    const cur = s[i];
    for (let d = (i === 0 ? 1 : 0); d < cur; d++) {
      if (!used[d]) unique += perm(10 - (i + 1), len - i - 1);
    }
    if (used[cur]) return n - unique;
    used[cur] = true;
  }

  return n - (unique + 1);
};

中文

题目概述

给定整数 n，统计区间 [1, n] 中至少包含一位重复数字的整数个数。

核心思路

先求补集更简单：统计 [1, n] 里“所有位都不重复”的数字数量，然后用
答案 = n - 不重复数量。

算法步骤

- 把 n 拆成数字数组。
- 先统计位数小于 len(n) 的不重复数字个数（排列数）。
- 再按位从左到右处理等长情况，尝试比当前位小且未使用的数字，累加后续排列数。
- 若当前位数字已被使用，说明前缀已重复，直接结束。
- 若整串都未重复，额外加上 n 本身。
- 最终返回 n - uniqueCount。

复杂度分析

时间复杂度：O(d^2)，其中 d 是位数。
空间复杂度：O(d)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int numDupDigitsAtMostN(int n) {
        char[] s = String.valueOf(n).toCharArray();
        int len = s.length;
        int unique = 0;

        for (int l = 1; l < len; l++) {
            unique += 9 * perm(9, l - 1);
        }

        boolean[] used = new boolean[10];
        for (int i = 0; i < len; i++) {
            int cur = s[i] - '0';
            for (int d = (i == 0 ? 1 : 0); d < cur; d++) {
                if (!used[d]) {
                    unique += perm(10 - (i + 1), len - i - 1);
                }
            }
            if (used[cur]) {
                return n - unique;
            }
            used[cur] = true;
        }

        return n - (unique + 1);
    }

    private int perm(int m, int k) {
        int ans = 1;
        for (int i = 0; i < k; i++) ans *= (m - i);
        return ans;
    }
}

func numDupDigitsAtMostN(n int) int {
    s := strconv.Itoa(n)
    length := len(s)
    unique := 0

    perm := func(m, k int) int {
        ans := 1
        for i := 0; i < k; i++ {
            ans *= (m - i)
        }
        return ans
    }

    for l := 1; l < length; l++ {
        unique += 9 * perm(9, l-1)
    }

    used := make([]bool, 10)
    for i := 0; i < length; i++ {
        cur := int(s[i] - '0')
        start := 0
        if i == 0 {
            start = 1
        }
        for d := start; d < cur; d++ {
            if !used[d] {
                unique += perm(10-(i+1), length-i-1)
            }
        }
        if used[cur] {
            return n - unique
        }
        used[cur] = true
    }

    return n - (unique + 1)
}

class Solution {
public:
    int perm(int m, int k) {
        int ans = 1;
        for (int i = 0; i < k; ++i) ans *= (m - i);
        return ans;
    }

    int numDupDigitsAtMostN(int n) {
        string s = to_string(n);
        int len = s.size();
        int unique = 0;

        for (int l = 1; l < len; ++l) {
            unique += 9 * perm(9, l - 1);
        }

        vector<bool> used(10, false);
        for (int i = 0; i < len; ++i) {
            int cur = s[i] - '0';
            for (int d = (i == 0 ? 1 : 0); d < cur; ++d) {
                if (!used[d]) {
                    unique += perm(10 - (i + 1), len - i - 1);
                }
            }
            if (used[cur]) return n - unique;
            used[cur] = true;
        }

        return n - (unique + 1);
    }
};

class Solution:
    def numDupDigitsAtMostN(self, n: int) -> int:
        s = list(map(int, str(n)))
        length = len(s)
        unique = 0

        def perm(m: int, k: int) -> int:
            ans = 1
            for i in range(k):
                ans *= (m - i)
            return ans

        for l in range(1, length):
            unique += 9 * perm(9, l - 1)

        used = [False] * 10
        for i, cur in enumerate(s):
            start = 1 if i == 0 else 0
            for d in range(start, cur):
                if not used[d]:
                    unique += perm(10 - (i + 1), length - i - 1)
            if used[cur]:
                return n - unique
            used[cur] = True

        return n - (unique + 1)

var numDupDigitsAtMostN = function(n) {
  const s = String(n).split('').map(Number);
  const len = s.length;
  let unique = 0;

  const perm = (m, k) => {
    let ans = 1;
    for (let i = 0; i < k; i++) ans *= (m - i);
    return ans;
  };

  for (let l = 1; l < len; l++) {
    unique += 9 * perm(9, l - 1);
  }

  const used = Array(10).fill(false);
  for (let i = 0; i < len; i++) {
    const cur = s[i];
    for (let d = (i === 0 ? 1 : 0); d < cur; d++) {
      if (!used[d]) unique += perm(10 - (i + 1), len - i - 1);
    }
    if (used[cur]) return n - unique;
    used[cur] = true;
  }

  return n - (unique + 1);
};