2376. Count Special Integers

HardMathDynamic Programming
Leetcode Link

Problem Description

The essence of this problem is to find how many positive integers up to a given number n have all distinct digits – that is, no digit is repeated within the number. For example, the number 12345 is a special number because all of its digits are unique, while 11345 is not because the digit 1 is repeated.

To compute this, we need to consider all integers from 1 to n and count only those that meet the criteria of having distinct digits. It's important to note that 0 cannot be a starting digit of any special number as the numbers are positive integers.

Intuition

To solve this problem efficiently without checking every number individually, we need to use combinatorics to count the number of potential combinations of distinct digits at different magnitudes (thousands, hundreds, tens, units, etc.).

Here's the general intuition behind the solution approach:

  • We define a helper function A(m, n) which calculates the number of permutations of m distinct elements taken n at a time. This is important for understanding how many distinct digit numbers we can create with a given set of digits.
  • We start by counting the number of special numbers for lengths less than the length of n. If n has m digits, we first count all special numbers with lengths from 1 to m-1 digits. For each of these lengths, the first digit can be chosen in 9 ways (1 through 9), and the remaining digits can be chosen using the A(m, n) function since the order matters and we cannot repeat digits.
  • For the numbers that have the same number of digits as n, we have to be careful not to exceed n. We do this by going digit by digit from the most significant to the least significant digit in n.
  • We maintain an array vis which represents which digits have been visited so far to ensure that we are only considering numbers with unique digits.
  • Working digit by digit from the highest to the lowest, for each digit in n, we count the number of special numbers we can form without exceeding that digit.
  • If at any point, we reach a digit in n that has already been used in the number we're forming, we stop the process because any larger numbers would not be special.
  • Finally, when we finish processing each digit, we have counted all the special numbers up to n.

Overall, the approach is to smartly count all possible combinations of distinct digits without having to enumerate each special number individually.

Learn more about Math and Dynamic Programming patterns.

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

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

Solution Approach

The provided solution implements a combinatorics-based approach backed by permutation mathematics and logical partitioning of the problem space. This approach utilizes an array to keep track of visited digits and a permutation function to count valid numbers. The implementation details are key to understanding how the solution works effectively to count special numbers.

Here's the step-by-step solution approach:

  • We define a permutation function A(m, n) which calculates permutations of m elements taken n at a time recursively. This is used to figure out how many arrangements are possible for a set of digits.

  • The variable vis is an array of boolean flags indicating which digits (0-9) have already been used in a number under construction. This way, we ensure the uniqueness of digits.

  • We create a variable ans to store the total count of special numbers and a list digits which contains the individual digits of n in reverse order for ease of processing from the lowest to the highest digit.

  • We count special numbers for lengths less than the length of n. For a number of length i, there are 9 options for the first digit (1-9) and then we calculate the arrangements of the remaining i-1 digits using the permutation function A(9, i - 1).

  • Next, we process digits with the same length as n. Starting from the most significant digit and moving towards the least significant, we count the number of special numbers smaller than n that can be formed with each digit.

    • For each digit in n (considered in reverse order), we iterate from the lowest allowed digit (1 if it's the most significant digit, and 0 otherwise) up to but not including the current digit v of n, using our A function to count permutations constrained by the number of distinct digits available and the length of the substring formed so far.

    • If we encounter a digit that has been already visited (vis[v] is true), it means we've already accounted for all special numbers that can be formed with the current prefix, and we break the loop.

    • We mark the digit we're currently at as visited (vis[v] = True).

    • If we reach the least significant digit, we perform one final check. If all digits were unique, we also count the number itself by incrementing ans by 1.

By combining these steps, the algorithm manages to count all distinct digits numbers up to n without enumerating each potentially vast set of numbers. The use of the permutation function significantly reduces the computational complexity by taking advantage of the properties of numbers and the definition of "special" in the problem.

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

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Example Walkthrough

Let's use the number n = 320 as an example to illustrate the solution approach described.

  1. Initial setup:

    • The number 320 has three digits.
    • We initialize ans to 0 for counting special numbers.
    • We define a permutation function A(m, n) that calculates permutations of m elements taken n at a time.
    • We prepare a vis array to mark digits that have been used.

  2. Counting numbers with fewer digits:

    • First, we count special numbers with one digit. There are 9 options (1-9), so 9 × A(9, 0) = 9.
    • Next, we count special numbers with two digits. The first digit has 9 options, and the second has 9 options (0-9, excluding the first digit), so 9 × A(9, 1) = 81.
    • Add these to ans for a subtotal of 9 + 81 = 90.

  3. Processing the same length as n:

    • Starting with the most significant digit, we have:

      1. Hundreds place: The first digit can be 1 or 2 because 3 is the hundreds digit of n. Each option allows for A(9, 2) permutations of the remaining digits.

        • When the first digit is 1, we can use any digit (0-9 excluding 1) for the tens and the units place: 1 × A(9, 2) = 72.
        • When the first digit is 2, it's the same situation: 1 × A(9, 2) = 72.
        • Add these to ans for a new subtotal: 90 + 72 + 72 = 234.

      2. Tens place: Next, we consider the digit 2 as fixed (from n) and look at the tens digit. No tens digits have been used yet (except 2), so we have options (0, 1). Each option allows for A(8, 1) permutations of the units digit.

        • For 0 as the tens digit: 1 × A(8, 1) = 8.
        • For 1 as the tens digit: 1 × A(8, 1) = 8.
        • Update ans: 234 + 8 + 8 = 250.

      3. Units place: Lastly, we fix the tens digit to 2 (from n) and consider the units digit. We can only use 0 or 1 without repeating any digits.

        • Both 0 and 1 are valid and lead to unique numbers, so we add 2 more to our answer: 250 + 2 = 252.

    • Since we have considered all the digits of n = 320, we conclude with ans = 252.

In our example, there are 252 positive integers less than or equal to 320 that have all distinct digits. This walkthrough demonstrates the effectiveness of using combinatorics and permutation mathematics to solve the problem without checking each number individually.

Solution Implementation

1class Solution:
2    def count_special_numbers(self, n: int) -> int:
3        # Recursive function to calculate permutations A(m, n) = m! / (m-n)!
4        def permutations(m, n):
5            if n == 0:
6                return 1
7            else:
8                return permutations(m, n - 1) * (m - n + 1)
9
10        # List to keep track of visited digits
11        visited = [False] * 10
12      
13        # Variable to store the count of special numbers
14        answer = 0
15      
16        # Convert the number into a list of its digits in reverse order
17        # so we can process the least significant digit first
18        digits = [int(c) for c in str(n)[::-1]]
19      
20        # Length of the number (number of digits)
21        num_length = len(digits)
22      
23        # Count all special numbers with length less than the length of n
24        for i in range(1, num_length):
25            answer += 9 * permutations(9, i - 1)
26
27        # Count special numbers with the same length as n        
28        for i in range(num_length - 1, -1, -1):
29            current_digit = digits[i]
30          
31            # First digit cannot be 0, others can
32            start = 1 if i == num_length - 1 else 0
33          
34            while start < current_digit:
35                if not visited[start]:
36                    answer += permutations(10 - (num_length - i), i)
37                start += 1
38          
39            # If the current digit has already been visited, stop the loop
40            if visited[current_digit]:
41                break
42          
43            # Mark the digit as visited
44            visited[current_digit] = True
45          
46            # If we're at the last digit and haven't broken the loop,
47            # then we need to account for this number itself being a special number
48            if i == 0:
49                answer += 1
50
51        return answer
52
53# Example usage:
54# sol = Solution()
55# print(sol.count_special_numbers(20))  # The output will be the count of special numbers less than or equal to 20
56
1class Solution {
2    public int countSpecialNumbers(int n) {
3        // Create a list to hold the individual digits of the number in reverse order
4        List<Integer> digits = new ArrayList<>();
5        while (n != 0) {
6            digits.add(n % 10);
7            n /= 10;
8        }
9
10        // Determine the number of digits in the number
11        int numDigits = digits.size();
12
13        // This will hold our final count of special numbers
14        int count = 0;
15
16        // Count special numbers with fewer digits than the input number
17        for (int i = 1; i < numDigits; ++i) {
18            count += 9 * permute(9, i - 1);
19        }
20
21        // Visit tracking array for digits
22        boolean[] visited = new boolean[10];
23
24        // Iterate over each digit, starting with the most significant digit
25        for (int i = numDigits - 1; i >= 0; --i) {
26            int currentValue = digits.get(i);
27            // Count the special numbers smaller than the current number at digit `i`
28            for (int j = i == numDigits - 1 ? 1 : 0; j < currentValue; ++j) {
29                if (!visited[j]) {
30                    count += permute(10 - (numDigits - i), i);
31                }
32            }
33            // If digit was seen before, no need to continue
34            if (visited[currentValue]) {
35                break;
36            }
37            // Mark the digit as visited
38            visited[currentValue] = true;
39            // If we've reached the least significant digit, include it in the count
40            if (i == 0) {
41                ++count;
42            }
43        }
44        return count;
45    }
46
47    // Recursive method to compute permutations, denoted as A(m, n) = m! / (m - n)!
48    private int permute(int m, int n) {
49        return n == 0 ? 1 : permute(m, n - 1) * (m - n + 1);
50    }
51}
52
1class Solution {
2public:
3    int countSpecialNumbers(int n) {
4        int answer = 0; // Holds the count of special numbers.
5        vector<int> digits; // Stores individual digits of the number n.
6
7        // Extract digits of number and store in reverse order.
8        while (n) {
9            digits.push_back(n % 10);
10            n /= 10;
11        }
12
13        int m = digits.size(); // Number of digits in n.
14        vector<bool> visited(10, false); // Flags to keep track of digits used.
15
16        // Count special numbers less than the given number with fewer digits.
17        for (int i = 1; i < m; ++i) {
18            answer += 9 * permutation(9, i - 1);
19        }
20
21        // Count the special numbers less than the given number with same number of digits.
22        for (int i = m - 1; i >= 0; --i) {
23            int currentDigit = digits[i];
24          
25            // Counting arrangements for each digit less than currentDigit.
26            for (int j = i == m - 1 ? 1 : 0; j < currentDigit; ++j) {
27                if (!visited[j]) {
28                    answer += permutation(10 - (m - i), i);
29                }
30            }
31          
32            // If currentDigit has already been seen, stop and exit.
33            if (visited[currentDigit]) {
34                break;
35            }
36          
37            // Mark this digit as used.
38            visited[currentDigit] = true;
39          
40            // If this is the last digit and hasn't been visited, include this number.
41            if (i == 0) {
42                ++answer;
43            }
44        }
45
46        // Return the total count of special numbers.
47        return answer;
48    }
49
50    // Helper function to calculate permutations, P(m, n) = m! / (m-n)!.
51    int permutation(int m, int n) {
52        if (n == 0) return 1; // Base case for permutation.
53        return permutation(m, n - 1) * (m - n + 1); // Recursive count of permutations.
54    }
55};
56
1// Global array to keep track of visited digits.
2const visited: boolean[] = new Array(10).fill(false);
3
4// Helper function to calculate permutations, P(m, n) = m! / (m-n)!.
5function permutation(m: number, n: number): number {
6    if (n === 0) return 1; // Base case for permutation.
7    return permutation(m, n - 1) * (m - n + 1); // Recursive count of permutations.
8}
9
10// Main function to count special numbers up to a given number n.
11function countSpecialNumbers(n: number): number {
12    let answer: number = 0; // Holds the count of special numbers.
13    const digits: number[] = []; // Stores individual digits of the number n in reverse order.
14
15    // Extract digits of n and store in reverse order.
16    while (n) {
17        digits.push(n % 10);
18        n = Math.floor(n / 10);
19    }
20
21    const m: number = digits.length; // The number of digits in n.
22
23    // Count special numbers less than n with fewer digits.
24    for (let i = 1; i < m; ++i) {
25        answer += 9 * permutation(9, i - 1);
26    }
27
28    // Count the special numbers less than n with the same number of digits.
29    for (let i = m - 1; i >= 0; --i) {
30        const currentDigit: number = digits[i];
31
32        // Counting arrangements for each digit less than currentDigit.
33        for (let j = i === m - 1 ? 1 : 0; j < currentDigit; ++j) {
34            if (!visited[j]) {
35                answer += permutation(10 - (m - i), i);
36            }
37        }
38
39        // If currentDigit has been seen before, break from the loop.
40        if (visited[currentDigit]) {
41            break;
42        }
43
44        // Mark the current digit as visited.
45        visited[currentDigit] = true;
46
47        // If last digit hasn't been visited, include this number in the count.
48        if (i === 0) {
49            ++answer;
50        }
51    }
52
53    // Reset the visited array for future calls to countSpecialNumbers.
54    visited.fill(false);
55
56    // Return the total count of special numbers.
57    return answer;
58}
59
Not Sure What to Study? Take the 2-min Quiz

What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?

Time and Space Complexity

The time complexity of the given code is primarily determined by two nested loops: an outer loop and an inner loop.

The outer loop runs for i from 1 to m, where m is the length of n in terms of number of digits. This loop runs in O(m).

Inside the outer loop, there is an inner loop that continues until j reaches the digit v. In the worst-case scenario, this loop could iterate 9 times (if v is 9 and j starts from 0). However, this doesn't run for every digit because once a repeated digit is detected, the loop breaks. Thus, this contributes less than O(9*m) complexity.

The function A(m, n) is a recursive implementation of arranging m elements in n places, which takes O(n) time since it calls itself recursively n times.

The combination of these loops and the recursive function A(m, n) means that the overall time complexity is O(m * 9 * n), simplifying to O(m^2) considering that n is bounded by m.

For space complexity, the code uses a vis list of constant size 10 to keep track of visited digits. Aside from this and some integer variables, there's no additional scaling with input size, making the space complexity O(1), or constant space.

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

Fast Track Your Learning with Our Quick Skills Quiz:

Breadth first search can be used to find the shortest path between two nodes in a directed graph.

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

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

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 đŸ‘šâ€đŸ«