Numbers With Repeated Digits

Hard
1298.

Numbers With Repeated Digits

Numbers With Repeated Digits is a hard coding problem on dynamic programming, math and combinatorics, asked in Amazon and Google interviews.

Given an integer n, return how many integers in the range [1, n] have at least one repeated digit — some digit appearing two or more times in their decimal form.

Example 1

Input
n = 20
Output
1
Explanation
Only 11.

Example 2

Input
n = 100
Output
10
Explanation
11, 22, 33, 44, 55, 66, 77, 88, 99 and 100.

Example 3

Input
n = 1000
Output
262

Constraints

  • 1 <= n <= 10^9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {number}
 */
var numDupDigitsAtMostN = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Numbers With Repeated Digits — Problem & Solution

Numbers With Repeated Digits solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Numbers With Repeated Digits is a hard coding problem on dynamic programming, math and combinatorics, asked in Amazon and Google interviews.

Problem statement

Given an integer n, return how many integers in the range [1, n] have at least one repeated digit — some digit appearing two or more times in their decimal form.

Example 1

Input: n = 20
Output: 1
Explanation: Only 11.

Example 2

Input: n = 100
Output: 10
Explanation: 11, 22, 33, 44, 55, 66, 77, 88, 99 and 100.

Example 3

Input: n = 1000
Output: 262

Constraints

  • 1 <= n <= 10^9

Hints for Numbers With Repeated Digits

  1. Hint 1

    Count the complement: numbers in [1, n] whose digits are all different, then subtract from n.

  2. Hint 2

    Numbers with fewer digits than n are easy: with L digits there are 9 * 9 * 8 * … of them (the first digit cannot be 0).

  3. Hint 3

    For numbers with as many digits as n, walk along n's digits: at position i, count unused digits smaller than n[i] (no leading zero), each followed by any arrangement of the remaining unused digits. Stop if n[i] was already used.

How to solve Numbers With Repeated Digits

Count the numbers ≤ n with all-distinct digits by permutation counting along the digits of n (a digit DP done in closed form), and subtract from n.

Approach

  1. Work with n + 1 and count distinct-digit numbers strictly below it; let its digits be s with length L.
  2. Add numbers with fewer digits: for each length len < L, 9 · P(9, len − 1), where P(a, b) = a!/(a−b)!.
  3. Walk s from the left with a set of used digits. At position i, for each digit x < s[i] (from 1 at the first position, from 0 later) that is not used, add P(9 − i, L − i − 1) — the ways to fill the rest with distinct unused digits.
  4. If s[i] is already used, stop; otherwise mark it used and continue.
  5. Return n − count.

Why it works

Each number below n + 1 with the same length agrees with it on a prefix and then has a smaller digit at the first difference; grouping by that position and digit counts each exactly once. After fixing i + 1 distinct digits, the remaining L − i − 1 positions take distinct digits from the 10 − (i + 1) = 9 − i unused ones, in P(9 − i, L − i − 1) ways. Once the prefix of s itself repeats a digit, every longer extension of it repeats too, so the walk can stop. Using n + 1 makes the 'strictly below' count include n itself.

Complexity

  • Time — O(L · 10) with L ≤ 10
  • Space — O(1)

Pitfalls

  • Leading zeros: the first digit ranges over 1–9, later digits over 0–9.
  • Forgetting to stop when a digit of n repeats — later positions would count numbers that share that repeated prefix.
  • Counting below n instead of up to n misses n itself (use n + 1, or add 1 when n has distinct digits).

Reference solution

Python

def numDupDigitsAtMostN(n: int) -> int:
    def perm(m: int, r: int) -> int:
        res = 1
        for i in range(r):
            res *= m - i
        return res

    digits = [int(c) for c in str(n + 1)]
    length = len(digits)
    unique = 0
    for size in range(1, length):
        unique += 9 * perm(9, size - 1)
    seen = set()
    for i, d in enumerate(digits):
        for x in range(1 if i == 0 else 0, d):
            if x not in seen:
                unique += perm(9 - i, length - i - 1)
        if d in seen:
            break
        seen.add(d)
    return n - unique

Java

static int ndPerm(int m, int r) {
    int res = 1;
    for (int i = 0; i < r; i++) res *= m - i;
    return res;
}

public static int numDupDigitsAtMostN(int n) {
    String s = String.valueOf((long) n + 1);
    int length = s.length();
    long unique = 0;
    for (int size = 1; size < length; size++) unique += 9L * ndPerm(9, size - 1);
    boolean[] seen = new boolean[10];
    for (int i = 0; i < length; i++) {
        int d = s.charAt(i) - '0';
        for (int x = i == 0 ? 1 : 0; x < d; x++) if (!seen[x]) unique += ndPerm(9 - i, length - i - 1);
        if (seen[d]) break;
        seen[d] = true;
    }
    return (int) (n - unique);
}

C++

static int ndPerm(int m, int r) {
    int res = 1;
    for (int i = 0; i < r; i++) res *= m - i;
    return res;
}

int numDupDigitsAtMostN(int n) {
    string s = to_string((long long)n + 1);
    int length = s.size();
    long long unique = 0;
    for (int size = 1; size < length; size++) unique += 9LL * ndPerm(9, size - 1);
    bool seen[10] = {false};
    for (int i = 0; i < length; i++) {
        int d = s[i] - '0';
        for (int x = i == 0 ? 1 : 0; x < d; x++) if (!seen[x]) unique += ndPerm(9 - i, length - i - 1);
        if (seen[d]) break;
        seen[d] = true;
    }
    return (int)(n - unique);
}

JavaScript

var numDupDigitsAtMostN = function(n) {
    var perm = function(m, r) {
        var res = 1;
        for (var i = 0; i < r; i++) res *= m - i;
        return res;
    };
    var s = String(n + 1);
    var length = s.length;
    var unique = 0;
    for (var size = 1; size < length; size++) unique += 9 * perm(9, size - 1);
    var seen = [false, false, false, false, false, false, false, false, false, false];
    for (var i = 0; i < length; i++) {
        var d = s.charCodeAt(i) - 48;
        for (var x = i === 0 ? 1 : 0; x < d; x++) if (!seen[x]) unique += perm(9 - i, length - i - 1);
        if (seen[d]) break;
        seen[d] = true;
    }
    return n - unique;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 402 dynamic programming problems · the whole catalogue

Learn the technique: Dynamic Programming