SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Description

Given a non-negative integer n, you are tasked with calculating how many numbers of length n have unique digits. The digits range from 0-9, and the length of the number varies from 0 to n.

The function should return the count of all possible numbers that can be formed using unique digits, where the number of digits is less than or equal to n.

Intuition

The problem can be approached by calculating how many valid numbers can be generated for a given length. If n = 0, the result is 1 because the only valid number is 0. For n = 1, we can have any of the digits from 0-9.

For n > 1, we need to consider that the first digit of the number can only be from 1-9, and the remaining digits must be selected from the remaining available digits, ensuring they are unique.

This recursive structure helps in reducing the problem step by step, where each reduction handles smaller lengths of the number.

Approach

1. Base Cases: If n = 0, return 1 because the only valid number is 0. If n = 1, return 10 because the valid numbers range from 0-9.
2. Recursive Case: For n > 1, compute the number of ways to form a valid number by multiplying the number of choices for each digit (9 choices for the first, 9 for the second, and so on).
3. Combine the results using recursion. For each step, compute the product of available digit choices and add it to the result from a previous step.
4. The recursion ensures that we handle the case for each n, reducing it until the base case is reached.

Complexity

Time Complexity:

O(n), where n is the input number. For each recursive call, we perform a constant amount of work to calculate the number of unique digits possible for that specific length.

Space Complexity:

O(n), due to the recursion stack.

Code

C++

class Solution {
public:
    int countNumbersWithUniqueDigits(int n) {
        if (n == 0) return 1;
        if (n == 1) return 10;
        int k = 9;
        for (int i = 0; i < n - 1; i++) {
            k *= (9 - i);
        }
        return k + countNumbersWithUniqueDigits(n - 1);
    }
};

Python

class Solution:
    def countNumbersWithUniqueDigits(self, n: int) -> int:
        if n == 0:
            return 1
        if n == 1:
            return 10
        k = 9
        for i in range(n - 1):
            k *= (9 - i)
        return k + self.countNumbersWithUniqueDigits(n - 1)

Java

class Solution {
    public int countNumbersWithUniqueDigits(int n) {
        if (n == 0) return 1;
        if (n == 1) return 10;
        int k = 9;
        for (int i = 0; i < n - 1; i++) {
            k *= (9 - i);
        }
        return k + countNumbersWithUniqueDigits(n - 1);
    }
}

JavaScript

/**
 * @param {number} n
 * @return {number}
 */
const countNumbersWithUniqueDigits = function (n) {
    if (n == 0) return 1;
    if (n == 1) return 10;
    let k = 9;
    for (let i = 0; i < n - 1; i++) {
        k *= (9 - i);
    }
    return k + countNumbersWithUniqueDigits(n - 1);
};