Count Numbers with Unique Digits

Medium
325.

Count Numbers with Unique Digits

Count Numbers with Unique Digits is a medium coding problem on dynamic programming, math and backtracking, asked in Amazon and Google interviews.

Given an integer n, return the count of numbers x with 0 <= x < 10^n that have all distinct digits.

Example 1

Input
n = 2
Output
91
Explanation
All 100 numbers below 100 except the nine repdigits 11, 22, …, 99.

Example 2

Input
n = 0
Output
1
Explanation
Only x = 0 satisfies 0 <= x < 1.

Example 3

Input
n = 3
Output
739

Constraints

  • 0 <= n <= 8
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 countNumbersWithUniqueDigits = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count Numbers with Unique Digits — Problem & Solution

Count Numbers with Unique Digits solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Count Numbers with Unique Digits is a medium coding problem on dynamic programming, math and backtracking, asked in Amazon and Google interviews.

Problem statement

Given an integer n, return the count of numbers x with 0 <= x < 10^n that have all distinct digits.

Example 1

Input: n = 2
Output: 91
Explanation: All 100 numbers below 100 except the nine repdigits 11, 22, …, 99.

Example 2

Input: n = 0
Output: 1
Explanation: Only x = 0 satisfies 0 <= x < 1.

Example 3

Input: n = 3
Output: 739

Constraints

  • 0 <= n <= 8

Hints for Count Numbers with Unique Digits

  1. Hint 1

    Count by digit length and add the counts up.

  2. Hint 2

    A number with exactly d digits has 9 choices for the leading digit and then 9, 8, 7, … for the rest.

  3. Hint 3

    Anything past ten digits is impossible — there are only ten distinct digits.

How to solve Count Numbers with Unique Digits

Count by digit length: a d-digit number with distinct digits has 9 · 9 · 8 · … · (11 - d) choices; sum over d up to min(n, 10), plus the ten one-digit numbers.

Approach

  1. Return 1 for n = 0.
  2. Start total = 10, current = 9; for d from 2 to min(n, 10), current *= 11 - d and add it.
  3. Return total.

Why it works

The leading digit cannot be 0 (9 choices), then each subsequent position avoids all earlier digits. Beyond ten digits no number can have distinct digits.

Complexity

  • Time — O(min(n, 10))
  • Space — O(1)

Pitfalls

  • The one-digit count is 10 (including 0), not 9.

Reference solution

Python

def countNumbersWithUniqueDigits(n: int) -> int:
    if n == 0:
        return 1
    total, current = 10, 9
    for digits in range(2, min(n, 10) + 1):
        current *= 11 - digits
        total += current
    return total

Java

public static int countNumbersWithUniqueDigits(int n) {
    if (n == 0) return 1;
    int total = 10, current = 9;
    for (int digits = 2; digits <= n && digits <= 10; digits++) {
        current *= 11 - digits;
        total += current;
    }
    return total;
}

C++

int countNumbersWithUniqueDigits(int n) {
    if (n == 0) return 1;
    int total = 10, current = 9;
    for (int digits = 2; digits <= n && digits <= 10; digits++) {
        current *= 11 - digits;
        total += current;
    }
    return total;
}

JavaScript

var countNumbersWithUniqueDigits = function(n) {
    if (n === 0) return 1;
    let total = 10, current = 9;
    for (let digits = 2; digits <= n && digits <= 10; digits++) {
        current *= 11 - digits;
        total += current;
    }
    return total;
};

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 · Backtracking