Count Numbers with Unique Digits

Tested Python solution for LeetCode 357 with 12 pytest cases. Generate a practice environment with lcpy.

LeetCode 357, Medium. Topics: Math, Dynamic Programming, Backtracking. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 12 parametrized pytest cases, and a playground notebook:

lcpy gen -n 357   # by problem number
lcpy gen -s count_numbers_with_unique_digits   # by problem name

​

Problem

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

​

Examples

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.

Input: n = 0
Output: 1

​

Constraints

• 0 <= n <= 8

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

class Solution:
    # Time: O(n)
    # Space: O(1)
    def count_numbers_with_unique_digits(self, n: int) -> int:
        if n == 0:
            return 1
        total = 10
        count = 9
        available = 9
        for _ in range(2, n + 1):
            count *= available
            available -= 1
            total += count
        return total

​

Complexity

Time	Space
O(n)	O(1)

​

Tags