357. Count Numbers with Unique Digits

MediumMathDynamic ProgrammingBacktracking
Leetcode Link

Problem Description

In this problem, we are given a non-negative integer n, and we are asked to find out how many integers there are with unique digits such that the integer x satisfies 0 <= x < 10^n. Unique digits mean that no digit in the number repeats. For example, the number 123 has unique digits, while the number 112 does not because the digit 1 is repeated.

Intuition

To solve this problem, we can approach it by counting the number of valid numbers rather than generating each possible number, which would be inefficient.

  • For n == 0, the only number we can have is 0 itself, hence only one unique number.
  • For n == 1, any digit from 0 to 9 is valid, which means there are 10 unique numbers (including 0).

As soon as n is greater than 1, we start with 10 possibilities (from 0 to 9) and choose the second digit. There are only 9 possible choices left for the second digit since it has to be different from the first (excluding the case where the first digit is 0, as we've counted that in n == 1). For the third digit, there's one less choice than for the second (since now two digits are taken), and so on.

The solution follows these steps for n > 1:

  • Start the answer with 10 cases (all single-digit numbers plus the number 0).
  • For each additional digit place, we multiply our current count of unique digits by the decreasing number of options available (starting from 9 for the second digit, 8 for the third, etc.).

The formula for the number of unique digit numbers that can be formed with i+1 digits is f(i+1) = f(i) * (10 - i) where f(i) is the number of unique digit numbers with i digits and i begins at 1 and increments until n-1.

The solution code uses a loop to count the number of unique digit numbers for each number of digits from 1 up to n and adds them up to accumulate the total count.

Learn more about Math, Dynamic Programming and Backtracking patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

How many ways can you arrange the three letters A, B and C?

Solution Approach

The implementation of the solution for counting unique digit numbers consists of the following steps:

  • Start by checking for the base cases. If n is 0, return 1 because only the number 0 fits the criteria. If n is 1, return 10 because the numbers 0 through 9 are the only valid possibilities and they all have unique digits.

  • For numbers with more than one digit (n > 1), we'll need to calculate the possibilities using a loop. Initialize the ans (answer) variable with 10, to cover the one-digit numbers. Also, initialize a variable cur to 9, representing the number of choices for the first digit, excluding 0.

  • Loop from 0 to n - 1. In each iteration, we will calculate the number of unique numbers that can be created with an additional digit. Multiply cur by 9 - i, where i is the current iteration's index. This represents the decrease in available choices as we fix more digits in the number.

  • Add the result of the multiplication to ans, updating it to include the count of unique numbers with the new number of digits.

  • Continue this process until the loop ends.

  • Finally, return ans, which now holds the total count of unique-digit numbers for all lengths up to n digits.

Python Solution Code

1class Solution:
2    def countNumbersWithUniqueDigits(self, n: int) -> int:
3        if n == 0:
4            return 1
5        if n == 1:
6            return 10
7        ans, cur = 10, 9
8        for i in range(n - 1):
9            cur *= 9 - i
10            ans += cur
11        return ans

This solution employs a mathematical pattern without using any complex data structures. The loop efficiently calculates the count for each number of digits, and the use of multiplication (cur *= 9 - i) within the loop follows the pattern of the decreasing number of choices for each subsequent digit.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Example Walkthrough

Let's illustrate the solution approach with n = 3. The task is to count numbers with unique digits where 0 <= x < 1000 (since 10^3 = 1000).

For n = 0, there's only one number, 0, so the answer is 1.

For n = 1, any single digit number, 0 to 9, is valid and unique. That's 10 possibilities.

Now, for n > 2, we need to calculate the possibilities for numbers having 2 and 3 digits.

  • Two-digit numbers (10 to 99):

    • Start with 10 total unique numbers from the n = 1 case.
    • For the first digit (tens place), we have 9 choices (1 to 9, as we're not including 0 here since that's accounted for in the n = 1 case).
    • For the second digit (ones place), we have 9 choices again because it can be any digit except the one chosen for the tens place. This includes 0.
    • So for two-digit numbers, we have 9 * 9 = 81 possibilities.
    • Now, our total is 10 + 81 = 91.

  • Three-digit numbers (100 to 999):

    • Continuing from 91 unique numbers.
    • For the first digit (hundreds place), we still have 9 choices (1 to 9).
    • For the second digit (tens place), we have 9 choices.
    • Now, for the third digit (ones place), we have 8 choices because two digits are already used.
    • Multiplying these together, for three-digit numbers, we have 9 * 9 * 8 = 648.
    • Our total now is 91 + 648 = 739.

Adding all these up, for n = 3, we would have 739 unique digit numbers where 0 <= x < 1000. Using the pattern described in the Solution Approach, the loop calculates this same total. The pseudo-code for the loop would look like:

  • Initialize ans with 10 (for n = 1).
  • For each additional digit place (i from 0 to n - 1 = 2):
    • set cur to 9 for the first iteration.
    • multiply cur with 9 - i to account for the already chosen digits.
    • add the result to ans
    • if i = 0 (2 digits), cur = 9 * 9, add 81 to ans; ans becomes 91
    • if i = 1 (3 digits), cur = 9 * 9 * 8, add 648 to ans; ans becomes 739

Therefore, for n = 3, the countNumbersWithUniqueDigits function returns 739.

Solution Implementation

1class Solution:
2    def countNumbersWithUniqueDigits(self, n: int) -> int:
3        # Base case: If n is 0, there's only one number (0 itself) that can be formed
4        if n == 0:
5            return 1
6        # Base case: If n is 1, the numbers 0-9 are all unique, so there are 10
7        if n == 1:
8            return 10
9      
10        # Initialize the count for unique digit numbers with the total for n = 1
11        unique_digit_numbers_count = 10
12        # Variable to keep track of the count of unique digits for the current number of digits
13        current_count = 9  # Starting with 9 because we have 1 to 9 as options for the first digit
14      
15        # Loop through the number of digits from 2 to n, as we have already covered n = 1
16        for i in range(n - 1):
17            # The count of unique numbers for the current digit length is reduced by one less option each time
18            # since we're using one more digit and can't repeat any of the lower digits.
19            current_count *= 9 - i
20            # Add the count for the current number of digits to the overall count
21            unique_digit_numbers_count += current_count
22      
23        # Return the total count of unique digit numbers for all lengths up to n
24        return unique_digit_numbers_count
25
1class Solution {
2
3    // This method counts the numbers with unique digits up to a certain length.
4    public int countNumbersWithUniqueDigits(int n) {
5        // If n is 0, there's only one number which is 0 itself
6        if (n == 0) {
7            return 1;
8        }
9      
10        // If n is 1, we have digits from 0 to 9, resulting in 10 unique numbers
11        if (n == 1) {
12            return 10;
13        }
14      
15        // Initialize answer with the count for n = 1
16        int answer = 10;
17      
18        // Current number of unique digits as we increase the length
19        int currentUniqueNumbers = 9;
20      
21        // Loop to calculate the number of unique digit numbers for lengths 2 to n
22        for (int i = 0; i < n - 1; ++i) {
23            // Compute the count for the current length by multiplying with the digits
24            // available considering we can't reuse any we have already used
25            currentUniqueNumbers *= (9 - i);
26          
27            // Add the current length's count to the total answer so far
28            answer += currentUniqueNumbers;
29        }
30      
31        // Return the total count of unique numbers with digits up to length n
32        return answer;
33    }
34}
35
1class Solution {
2public:
3    int countNumbersWithUniqueDigits(int n) {
4        // Base cases:
5        // If n is 0, there's only 1 number (0 itself)
6        if (n == 0) return 1;
7        // If n is 1, there are 10 unique digit numbers (0 to 9)
8        if (n == 1) return 10;
9      
10        // Start with the count for a 1-digit number
11        int count = 10;
12
13        // Current number of unique digits we can use starting from 9
14        int uniqueDigits = 9;
15      
16        // Loop through the number of digits from 2 up to n
17        for (int i = 2; i <= n; i++) {
18            // Calculate the number of unique numbers that can be formed with i digits
19            // by multiplying the current number of unique digits we can use
20            uniqueDigits *= (11 - i);
21            // Add the count of unqiue numbers for the current number of digits to the total count
22            count += uniqueDigits;
23        }
24      
25        // Return the total count of numbers with unique digits
26        return count;
27    }
28};
29
1/**
2 * Counts the numbers with unique digits up to the given number of digits n.
3 * @param {number} n - The number of digits to consider.
4 * @returns {number} - The count of numbers with unique digits.
5 */
6function countNumbersWithUniqueDigits(n: number): number {
7    // Base case for 0 digits
8    if (n === 0) return 1;
9
10    // Base case for 1 digit
11    if (n === 1) return 10;
12  
13    // Initialize count with the total for a single digit
14    let count: number = 10;
15  
16    // Initialize uniqueDigits with the possible unique digits (9, not including 0)
17    let uniqueDigits: number = 9;
18  
19    // Iterate through the number of digits from 2 up to n
20    for (let i: number = 2; i <= n; i++) {
21        // Calculate the count for the current digit position by multiplying with the
22        // remaining unique digits (10 - i: since one digit is already used)
23        uniqueDigits *= (11 - i);
24        // Accumulate the count for the current number of digits
25        count += uniqueDigits;
26    }
27  
28    // Return the total count of numbers with unique digits
29    return count;
30}
31
Not Sure What to Study? Take the 2-min Quiz๏ผš

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Time and Space Complexity

The provided Python code defines a function countNumbersWithUniqueDigits which calculates the number of n-digit integers that have unique digits.

  • Time Complexity: The time complexity of the function is primarily determined by the for loop that iterates n - 1 times. Within the for loop, there are only constant-time operations. Therefore, the overall time complexity is O(n).

  • Space Complexity: The space complexity of the function is O(1) because the space used does not grow with the input size n. The function only uses a constant amount of additional space for variables ans and cur.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What data structure does Breadth-first search typically uses to store intermediate states?

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

Backtracking 1

Backtracking Template Prereq DFS with States problems dfs_with_states Combinatorial search problems Combinatorial search problems involve finding groupings and assignments of objects that satisfy certain conditions Finding all permutations combinations subsets and solving Sudoku are classic combinatorial problems The time complexity of combinatorial problems often grows rapidly with the size of

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ