Count Numbers with Unique Digits - Practice Coding Problems

Count Numbers with Unique Digits - Problem

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

A number has unique digits if no digit is repeated in the number. For example, 123 has unique digits but 121 does not.

Input & Output

Example 1 — Small Case

$ Input: n = 2

› Output: 91

💡 Note: Count all numbers from 0 to 99 with unique digits: single digits (0-9) = 10, two-digits with unique digits (10,12,13,...,98) = 81. Total = 10 + 81 = 91

Example 2 — Minimal Case

$ Input: n = 0

› Output: 1

💡 Note: Range is [0, 1), so only number 0 exists, which has unique digits

Example 3 — Larger Case

$ Input: n = 3

› Output: 739

💡 Note: Numbers 0 to 999: 1-digit = 10, 2-digit = 81, 3-digit = 648. Total = 10 + 81 + 648 = 739

Constraints

0 ≤ n ≤ 8

Visualization

Tap to expand

Understanding the Visualization

Input

Given n=2, find count in range [0, 100)

Process

Count by digit length: 1-digit + 2-digit numbers

Output

Total count of unique digit numbers

Key Takeaway

🎯 Key Insight: Use permutation formula P(10,k) to count directly instead of checking every number

Asked in

G Google 25 f Facebook 18

The key insight is to use mathematical permutations instead of checking every number. For k-digit numbers, the first digit has 9 choices (1-9), and each subsequent digit has one fewer choice from the remaining unused digits. Best approach uses mathematical formula with Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Backtracking with Pruning	O(10!)	O(n)	Build numbers digit by digit, tracking used digits
Brute Force Check Every Number	O(10^n × n)	O(n)	Check each number from 0 to 10^n-1 for unique digits
Mathematical Permutation	O(n)	O(1)	Calculate count using mathematical permutations without generating numbers

Backtracking with Pruning — Algorithm Steps

Start with empty number
Try each available digit at current position
Recursively build remaining positions
Count complete valid numbers

Visualization

Tap to expand

Step-by-Step Walkthrough

Choose First

Pick first digit from 1-9 (can't be 0)

Choose Next

Pick remaining digits from unused set

Count & Backtrack

Count valid numbers, backtrack when done

Code -

solution.c — C

#include <stdio.h>
#include <stdbool.h>

int backtrack(int pos, int n, bool used[]) {
    if (pos >= n) return 0;
    
    int count = 1; // Count current number (even if incomplete)
    
    for (int digit = 0; digit < 10; digit++) {
        if (used[digit]) continue;
        if (pos == 0 && digit == 0) continue; // First digit cannot be 0
        
        used[digit] = true;
        count += backtrack(pos + 1, n, used);
        used[digit] = false;
    }
    
    return count;
}

int solution(int n) {
    if (n == 0) return 1;
    
    // Count single digit numbers (0-9)
    int result = 10;
    
    // Count multi-digit numbers
    if (n > 1) {
        bool used[10] = {false};
        result += backtrack(0, n, used);
    }
    
    return result;
}

int main() {
    int n;
    scanf("%d", &n);
    printf("%d\n", solution(n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(10!)

At most 10 factorial permutations to explore

✓ Linear Growth

Space Complexity

O(n)

Recursion stack depth and used digits array

⚡ Linearithmic Space

23.0K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Backtracking with Pruning — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler