LeetCode 357: Count Numbers with Unique Digits Solution in Python – A Step-by-Step Guide

What Is LeetCode 357: Count Numbers with Unique Digits?

In LeetCode 357: Count Numbers with Unique Digits, you’re given an integer n, and your task is to count all numbers with unique digits from 1 digit up to n digits long, excluding leading zeros for numbers with more than one digit. A number has unique digits if no digit repeats (e.g., 123 is valid, but 121 is not). For example, with n = 2, valid numbers include 1 to 9 (single-digit) and 10, 12, 13, ..., 98 (two-digit), totaling 91.

Problem Statement

• Input: An integer n (number of digits).
• Output: An integer—the count of numbers with unique digits up to n digits.
• Rules:
• Digits must be unique within each number (0-9).
• Numbers from 1 to 10^n - 1 (but capped by constraint).
• No leading zeros for multi-digit numbers.

Constraints

• 0 <= n <= 8

Examples

• Input: n = 2
• Output: 91
• Why: 1-digit (9: 1-9) + 2-digit (81: 10, 12, ..., 98) = 91.
• Input: n = 1
• Output: 10
• Why: 0-9 (10 numbers).
• Input: n = 0
• Output: 1
• Why: Only 0 (empty number considered as 0).

Understanding the Problem: Counting Unique Numbers

To solve LeetCode 357: Count Numbers with Unique Digits in Python, we need to count all numbers with unique digits up to n digits long. A brute force approach—generating all numbers and checking each—would take O(10^n) time, which is impractical for n up to 8 (10⁸ numbers). Instead, we’ll use smarter methods:

• Best Solution (Combinatorial Formula): O(1) time, O(1) space—direct calculation.
• Alternative Solution (Dynamic Programming): O(n) time, O(n) space—iterative build-up.

Let’s dive into the Best Solution—combinatorial formula—and break it down step-by-step.

Best Solution: Combinatorial Formula

Why This Is the Best Solution

The combinatorial formula approach is the top choice because it’s blazing fast—O(1) time and O(1) space—using a mathematical insight to count unique-digit numbers directly without iteration. It leverages permutation logic to calculate choices for each digit position, accounting for the no-leading-zero rule. It’s like figuring out how many unique license plates you can make with a fixed length—quick and precise!

How It Works

Here’s the strategy:

• Step 1: Handle Edge Cases:
• n = 0: Return 1 (just 0).
• n > 10: Cap at 10 (only 10 digits available: 0-9).
• Step 2: First Digit:
• Can’t be 0, so 9 choices (1-9).
• Step 3: Remaining Digits:
• For each subsequent position, choose from remaining digits (9, 8, ..., down to 10-n+1).
• Total choices: 9 * 9 * 8 * ... * (10-n+1).
• Step 4: Formula:
• Single-digit: 9 + 1 (1-9 + 0).
• Multi-digit: 9 * product of (9 down to 10-n+1).
• Step 5: Return:
• Compute and return total.

Step-by-Step Example

Example: n = 2

• Step 1: Edge Cases:
• n = 2 ≤ 10, proceed.
• Step 2: First Digit:
• 9 choices (1-9).
• Step 3: Second Digit:
• 9 remaining (0-9 minus first digit): 9 choices.
• Step 4: Calculate:
• Total = 9 * 9 = 81 (2-digit).
• Add single-digit: 81 + 9 (1-9) + 1 (0) = 91.
• Result: 91.

Example: n = 1

• Step 1: n = 1.
• Step 2: Only single-digit: 9 (1-9) + 1 (0) = 10.
• Result: 10.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

Copy codeclass Solution:
    def countNumbersWithUniqueDigits(self, n: int) -> int:
        # Step 1: Handle edge cases
        if n == 0:
            return 1
        if n > 10:  # Cap at 10 digits (0-9)
            n = 10

        # Step 2: First digit (1-9)
        ans = 9

        # Step 3: Remaining digits
        available = 9  # Choices after first digit
        for i in range(n - 1):
            ans *= available
            available -= 1

        # Step 4: Add single-digit case
        ans += 1  # For n=1 case (0)
        if n > 1:
            ans += 9  # Add 1-9 for single-digit

        return ans

• Line 4-7: Handle n = 0 and cap at 10.
• Line 10: Start with 9 for first digit.
• Line 13-15: Multiply by remaining choices (9, 8, ...).
• Line 18-20: Adjust for single-digit numbers.
• Line 22: Return total count.
• Time Complexity: O(1)—constant iterations (n ≤ 10).
• Space Complexity: O(1)—few variables.

This is a counting shortcut genius!

Alternative Solution: Dynamic Programming

Why an Alternative Approach?

The dynamic programming approach offers an iterative perspective—O(n) time, O(n) space—building the count step-by-step using a DP array. It’s more educational and adaptable to variations, though less efficient than the formula. It’s like counting unique numbers digit by digit, learning as you go—systematic and insightful!

How It Works

• Step 1: dp[i]: Count of unique-digit numbers with i digits.
• Step 2: Base cases:
• dp[0] = 1 (0).
• dp[1] = 10 (0-9).
• Step 3: Recurrence:
• For i > 1, dp[i] = dp[i-1] * (11 - i) (adjust for available digits).
• Step 4: Sum up to n digits.

Step-by-Step Example

Example: n = 2

• Step 1: dp = [1, 10, 0].
• Step 2:
• dp[0] = 1 (0).
• dp[1] = 10 (0-9).
• Step 3:
• i = 2: dp[2] = dp[1] * (11-2) = 10 * 9 = 90.
• Step 4: Sum: 1 + 10 + 80 = 91 (adjust for overlap: 90 two-digit + 1 single-digit + 0).
• Result: 91.

Code for DP Approach

Copy codeclass Solution:
    def countNumbersWithUniqueDigits(self, n: int) -> int:
        # Step 1: Handle edge cases and initialize DP
        if n == 0:
            return 1
        if n > 10:
            n = 10
        dp = [0] * (n + 1)

        # Step 2: Base cases
        dp[0] = 1  # 0
        dp[1] = 10  # 0-9

        # Step 3: Fill DP
        for i in range(2, n + 1):
            dp[i] = dp[i-1] * (11 - i)

        # Step 4: Return sum up to n
        return sum(dp[:n+1]) - (1 if n > 1 else 0)  # Adjust overlap

• Line 11-12: Base cases.
• Line 15-16: Fill DP with recurrence.
• Line 19: Sum and adjust for correct count.
• Time Complexity: O(n)—linear fill.
• Space Complexity: O(n)—DP array.

It’s a step-by-step counter!

Comparing the Two Solutions

• Combinatorial Formula (Best):
• Pros: O(1) time, O(1) space, fast and direct.
• Cons: Less flexible for variations.
• Dynamic Programming (Alternative):
• Pros: O(n) time, O(n) space, intuitive and adaptable.
• Cons: Slower, more space.

Formula wins for speed and simplicity.

Additional Examples and Edge Cases

• n = 3: 739 (9*9*8 + 9 + 1).
• n = 0: 1.
• n = 11: Capped at 10, 3628800.

Both handle these perfectly.

Complexity Breakdown

• Formula: Time O(1), Space O(1).
• DP: Time O(n), Space O(n).

Formula’s efficiency shines.

Key Takeaways

• Formula: Math is magic!
• DP: Build it up!
• Unique Digits: Count choices.
• Python Tip: Loops optimize—see [Python Basics](/python/basics).

Final Thoughts: Count the Uniques

LeetCode 357: Count Numbers with Unique Digits in Python is a counting conundrum. The formula approach tallies with flair, while DP offers a learning path. Want more counting fun? Try LeetCode 91: Decode Ways or LeetCode 338: Counting Bits. Ready to count? Head to Solve LeetCode 357 on LeetCode and tally those uniques today!