Numbers With Repeated Digits

hard digit dp bitmask combinatorics

Problem

Given an integer n, return the number of positive integers in the range [1, n] that have at least one repeated digit.

Inputn = 100

Output10

The numbers with a repeated digit in [1, 100] are 11, 22, 33, 44, 55, 66, 77, 88, 99 and 100 — exactly 10 of them.

n (1 to 1,000,000,000)

def num_dup_digits_at_most_n(n):
    digits = [int(c) for c in str(n)]
    L = len(digits)
    # Count integers in [1, n] with ALL DISTINCT digits.
    unique = 0
    # Part 1: numbers with fewer digits than n.
    for k in range(1, L):
        cur = 9
        for j in range(1, k):
            cur *= (10 - j)
        unique += cur
    # Part 2: same length as n, prefix-by-prefix.
    used = set()
    for i, d in enumerate(digits):
        lo = 1 if i == 0 else 0
        for x in range(lo, d):
            if x in used:
                continue
            rest = 1
            for j in range(L - i - 1):
                rest *= (10 - i - 1 - j)
            unique += rest
        if d in used:
            break
        used.add(d)
    else:
        unique += 1  # n itself has all distinct digits
    return n - unique

function numDupDigitsAtMostN(n) {
  const digits = String(n).split("").map(Number);
  const L = digits.length;
  let unique = 0;
  // Part 1: numbers with fewer digits than n.
  for (let k = 1; k < L; k++) {
    let cur = 9;
    for (let j = 1; j < k; j++) cur *= (10 - j);
    unique += cur;
  }
  // Part 2: same length as n, prefix-by-prefix.
  const used = new Set();
  let broke = false;
  for (let i = 0; i < L; i++) {
    const d = digits[i];
    const lo = i === 0 ? 1 : 0;
    for (let x = lo; x < d; x++) {
      if (used.has(x)) continue;
      let rest = 1;
      for (let j = 0; j < L - i - 1; j++) rest *= (10 - i - 1 - j);
      unique += rest;
    }
    if (used.has(d)) { broke = true; break; }
    used.add(d);
  }
  if (!broke) unique += 1; // n itself has all distinct digits
  return n - unique;
}

class Solution {
    public int numDupDigitsAtMostN(int n) {
        char[] s = String.valueOf(n).toCharArray();
        int L = s.length, unique = 0;
        // Part 1: numbers with fewer digits than n.
        for (int k = 1; k < L; k++) {
            int cur = 9;
            for (int j = 1; j < k; j++) cur *= (10 - j);
            unique += cur;
        }
        // Part 2: same length as n, prefix-by-prefix.
        boolean[] used = new boolean[10];
        boolean broke = false;
        for (int i = 0; i < L; i++) {
            int d = s[i] - '0';
            int lo = (i == 0) ? 1 : 0;
            for (int x = lo; x < d; x++) {
                if (used[x]) continue;
                int rest = 1;
                for (int j = 0; j < L - i - 1; j++) rest *= (10 - i - 1 - j);
                unique += rest;
            }
            if (used[d]) { broke = true; break; }
            used[d] = true;
        }
        if (!broke) unique += 1; // n itself has all distinct digits
        return n - unique;
    }
}

int numDupDigitsAtMostN(int n) {
    string s = to_string(n);
    int L = s.size(), unique = 0;
    // Part 1: numbers with fewer digits than n.
    for (int k = 1; k < L; k++) {
        int cur = 9;
        for (int j = 1; j < k; j++) cur *= (10 - j);
        unique += cur;
    }
    // Part 2: same length as n, prefix-by-prefix.
    bool used[10] = {false};
    bool broke = false;
    for (int i = 0; i < L; i++) {
        int d = s[i] - '0';
        int lo = (i == 0) ? 1 : 0;
        for (int x = lo; x < d; x++) {
            if (used[x]) continue;
            int rest = 1;
            for (int j = 0; j < L - i - 1; j++) rest *= (10 - i - 1 - j);
            unique += rest;
        }
        if (used[d]) { broke = true; break; }
        used[d] = true;
    }
    if (!broke) unique += 1; // n itself has all distinct digits
    return n - unique;
}

Explanation

Counting numbers with a repeated digit directly is messy, so we flip the problem: it is much easier to count numbers with all distinct digits and then subtract from n. This is called complementary counting — the answer is n - (count of all-distinct numbers in [1, n]).

Part 1 counts all-distinct numbers that are shorter than n. A k-digit number can pick 9 choices for the leading digit (no leading zero) and then fewer and fewer choices as digits get used up: 9 × 9 × 8 × ..., computed by the inner product.

Part 2 handles numbers with the same length as n, going position by position while keeping the prefix tied to n. At each position we place an unused digit smaller than n's digit there and fill the rest with distinct digits, counting rest permutations of the remaining slots. We track a used set of digits already fixed.

If n's own digit at some position was already used (a repeat in n itself), the bounded path can't continue, so we stop. Otherwise, if every digit of n stays distinct, n counts too and we add 1.

Example: n = 100. The all-distinct count works out so that n - unique = 10, namely 11, 22, ..., 99 and 100. With at most ~10 digits, this runs in O(D^2).

Time: O(D²) Space: O(D)