Is Count Numbers with Unique Digits easy or hard?

The problem is rated Medium because the brute force idea is straightforward but recognizing the permutation pattern requires combinatorial reasoning. Once the pattern is identified, the implementation becomes very short and efficient.

How to solve Count Numbers with Unique Digits in O(n)?

Iterate over digit lengths from 1 to n and compute permutations. For length k, the count is 9 × 9 × 8 × ... for k digits because each new digit has fewer choices. Accumulate these counts to get the total number of valid integers.

Count Numbers with Unique Digits Python or Java solution?

Python solutions commonly implement backtracking with a visited set or use a simple loop to compute permutations. Java and C++ implementations often use the mathematical approach with iterative multiplication to maintain O(n) time and O(1) space.

What is the best approach for Count Numbers with Unique Digits?

The mathematical permutation approach is the most efficient. It counts how many valid digit permutations exist for each length instead of generating numbers. This runs in O(n) time with O(1) space and stops after 10 digits because only 10 unique digits exist.

Is Count Numbers with Unique Digits asked at Google/Amazon/Meta?

Permutation and combinatorics counting problems like this appear in interviews at large companies including Google and Amazon. The question tests understanding of digit constraints, permutations, and recognizing when enumeration can be replaced by counting.

What data structure is used in Count Numbers with Unique Digits?

The optimal solution mainly uses mathematical counting and does not require complex data structures. A backtracking implementation typically uses a boolean array or set to track which digits have already been used.

What is the time complexity of Count Numbers with Unique Digits?

The optimal permutation-based solution runs in O(n) time and O(1) space since it only multiplies decreasing digit choices for each length up to n. A backtracking solution can take up to O(10!) time because it explores permutations of digits.

Description Hints 5 Solution Video 12:53

357. Count Numbers with Unique Digits

Medium56.1% acceptance5 companies

Given an integer n, return the count of all numbers with unique digits, x, where 0 <= x < 10ⁿ.

Example 1:

Input: n = 2
Output: 91
Explanation: The answer should be the total numbers in the range of 0 ≤ x < 100, excluding 11,22,33,44,55,66,77,88,99

Example 2:

Input: n = 0
Output: 1

Constraints:

0 <= n <= 8

Asked at 5 companies

Google Amazon Microsoft Meta Bloomberg

Topics

Hints open one at a time

Hint 1

A direct way is to use the backtracking approach.

Hint 2

Backtracking should contains three states which are (the current number, number of steps to get that number and a bitmask which represent which number is marked as visited so far in the current number). Start with state (0,0,0) and count all valid number till we reach number of steps equals to 10ⁿ.

Hint 3

This problem can also be solved using a dynamic programming approach and some knowledge of combinatorics.

Hint 4

Let f(k) = count of numbers with unique digits with length equals k.

Hint 5

f(1) = 10, ..., f(k) = 9 * 9 * 8 * ... (9 - k + 2) [The first factor is 9 because a number cannot start with 0].

12:53

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution