LeetCode 3032: Count Numbers With Unique Digits II Solution

Master LeetCode problem 3032 (Count Numbers With Unique Digits II), a easy challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

3032. Count Numbers With Unique Digits II

Easy

Hash Table Math Dynamic Programming

Problem Explanation

Explanation:

To solve this problem, we can use backtracking to generate all possible numbers with unique digits up to a given number n. We will start from 0 and explore all possible digits that can be appended to the current number while ensuring that the digits are unique.

Algorithm:

Initialize a counter to keep track of the count of unique digit numbers.
Start from the number 0 and explore all possible digits that can be appended to it.
For each digit from 1 to 9, check if it has already been used in the current number. If not, append the digit to the current number and increment the count.
Recursively explore all possible digits that can be appended to the current number.
Backtrack by removing the last digit appended before exploring other digits.
Continue this process until we reach the number n.
Return the count of unique digit numbers.

Time Complexity:

The time complexity of this approach is O(9^n) where n is the given number.

Space Complexity:

The space complexity is O(n) for the recursive call stack.

: :

Solution Code

class Solution {
    public int countNumbersWithUniqueDigits(int n) {
        if (n == 0) return 1;
        int count = 1; // for the number 0
        for (int i = 1; i <= 9; i++) {
            count += backtrack(i, n, new boolean[10]);
        }
        return count;
    }
    
    private int backtrack(int num, int n, boolean[] used) {
        if (num > Math.pow(10, n) - 1) {
            return 0;
        }
        
        int count = 1;
        for (int i = 0; i <= 9; i++) {
            if (!used[i]) {
                used[i] = true;
                count += backtrack(num * 10 + i, n, used);
                used[i] = false;
            }
        }
        return count;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 3032 (Count Numbers With Unique Digits II)?

This page provides optimized solutions for LeetCode problem 3032 (Count Numbers With Unique Digits II) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 3032 (Count Numbers With Unique Digits II)?

The time complexity for LeetCode 3032 (Count Numbers With Unique Digits II) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 3032 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 3032 in Java, C++, or Python.

Back to LeetCode Solutions