algoadvance

Leetcode 357. Count Numbers with Unique Digits

Problem Statement

Given a non-negative integer n, return the count of all numbers with unique digits, x, where 0 ≤ x < 10^n.

Clarifying Questions

1. Can n be 0?
   • Yes, n can be 0.
2. What is the range of n?
   • n is a non-negative integer, typically n <= 10 because 10^n will have more digits than can fit in a standard integer.
3. What should be the output if n is 0?
   • If n is 0, the count of numbers with unique digits is 1 (0 itself).

Strategy

To solve this problem, we can use a mathematical approach rather than generating each number and checking its uniqueness. Let’s break down the idea:

• If n is greater than 10, we can’t have more than 10 unique digits because there are only 10 digits (0-9).
• For each digit length i from 1 to n, we calculate the number of unique numbers of length i.
• We use combinatorics to calculate the number of valid unique digit numbers of each length. We use a factorial-like approach because we need to pick unique digits in decreasing order.

Steps:

1. Base Case:
   • If n is 0, return 1.
2. Initialization:
   • Start by counting the one-digit numbers: there are 10 unique one-digit numbers (0 through 9).
3. Use a loop to calculate unique digit numbers for lengths 2 to n:
   • For length 2, there are 9 * 9 possible numbers (because the first digit can’t be 0).
   • For length 3, there are 9 * 9 * 8 possible numbers (because the first digit can’t be 0 and the second digit can be any of the 9 remaining digits, the third digit can be any of the 8 remaining digits).

Repeat this pattern up to n.

Code

public class Solution {
    public int countNumbersWithUniqueDigits(int n) {
        if (n == 0) return 1;
        int uniqueDigitsCount = 10; // For n = 1, there are 10 unique digits (0-9)
        int availableDigits = 9;
        int currentCount = 9;
        
        for (int i = 2; i <= n && availableDigits > 0; i++) {
            currentCount *= availableDigits;
            uniqueDigitsCount += currentCount;
            availableDigits--;
        }
        
        return uniqueDigitsCount;
    }
}

Time Complexity

The time complexity of the solution is O(n), where n is the input number. This is because the maximum number of iterations the loop will run is n.

The space complexity is O(1) because we are using a constant amount of extra space to store the counts and the factorial-like computations.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?