2999. Count the Number of Powerful Integers


Problem Description

The problem presents us with the task of finding how many numbers in a given range [start..finish] are considered powerful. A number is powerful if it satisfies two conditions:

  1. It ends with a given string s, which represents a positive integer suffix.
  2. Each digit of this number is less than or equal to a given limit.

In other words, we're looking for all the numbers between start and finish that have s as their ending digits (suffix) and do not exceed the limit in any of their other digits.

This problem is clearly asking for careful manipulation of strings and numbers to match patterns under certain constraints. It is non-trivial because it requires understanding how to iterate over a large range of numbers, ensure the suffix condition is satisfied, and simultaneously take care of the digit limit.

Intuition

When tackling this problem, a brute force approach that checks each number in the [start..finish] range for powerfulness might work but will likely be inefficient. Instead, we can think of a more optimized approach that focuses on the suffix and limits for a potential performance gain.

The key intuition here is to:

  • Perform the count on a digit by digit basis, moving left from the suffix 's', which we know must be at the end of every powerful integer.
  • Optimize the counting process by leveraging the bounded nature of our digits (they must be less than or equal to limit) and the fact that we're interested in numbers that only end in a particular suffix.
  • Use dynamic programming to avoid re-computing the count for numbers with the same prefix digits. This is typically done using memoization or tabulation. In the provided solution, memoization via a cache is used.

The provided solution uses a depth-first search (DFS) recursive approach with memoization to systematically construct possible digits from right to left, checking if they can be part of a powerful number that fits within our [start..finish] band. It constructs potential powerful numbers, determines whether they fall within the range, and counts them accordingly.

Learn more about Math and Dynamic Programming patterns.

Solution Approach

The solution to this problem involves a recursive depth-first search (dfs) function that constructs numbers digit by digit from the left, incorporating a few optimization strategies.

Here's a step-by-step breakdown of how the algorithm works:

  1. Memoization: To avoid recalculating the powerful number count for the same digit positions with similar constraints, we use the @cache decorator, a Python feature that stores the result of expensive function calls and returns the cached result when the same inputs occur again.

  2. Construction of Powerful Numbers: The dfs function is used to create numbers by adding one digit at a time from left to right. It stops adding digits when the current number's length equals the length of the suffix s.

    • Parameters of dfs:
      • pos: Current digit position we're trying to fill.
      • lim: A boolean that indicates whether we are restricted by the current prefix of the target number (True if we must follow the exact digits of t up to the current position, False otherwise).
  3. Suffix Checking: Once the length of the number being constructed equals the length of s, the function checks if s is a suffix of the current number. If lim is False, we're not restricted by t anymore and can increment our count freely.

  4. Limit enforcement and Recurrence: If adding more digits is possible, the upper bound for our current digit is determined by the minimum of the current digit in t (if lim is True, meaning we are still bound by the pre-existing digits of t) and the limit. Then, dfs recurses for each digit from 0 to up, potentially updating lim.

  5. Computing Counts for Start and Finish: The function dfs is called for both start - 1 and finish. We subtract 1 from start to simplify the computation by including the start value in our count. This effectively calculates the total powerful numbers up to start - 1 and separately up to finish, and we get the count in our range [start..finish] by taking the difference.

  6. Cache Clearing Between Calls: After calculating the count for start - 1, we clear the cache before calculating for finish because the lim parameter changes based on the different ranges.

Here's the relevant code section annotated with these steps:

1class Solution:
2    def numberOfPowerfulInt(self, start: int, finish: int, limit: int, s: str) -> int:
3        @cache
4        def dfs(pos: int, lim: int):
5            if len(t) < n:
6                return 0
7            if len(t) - pos == n:
8                return int(s <= t[pos:]) if lim else 1
9            up = min(int(t[pos]) if lim else 9, limit)
10            ans = 0
11            for i in range(up + 1):
12                ans += dfs(pos + 1, lim and i == int(t[pos]))
13            return ans
14
15        n = len(s)
16        t = str(start - 1)
17        a = dfs(0, True)
18        dfs.cache_clear()
19        t = str(finish)
20        b = dfs(0, True)
21        return b - a

In summary, the algorithm effectively enumerates all possible powerful numbers within provided constraints by delicate digit manipulation and optimization through memoization, cleverly avoiding any redundant computation.

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

Which data structure is used to implement priority queue?

Example Walkthrough

To illustrate the solution approach, let's use an example where the search range is [start..finish] = [123, 130], the limit for each digit is 3, and the number must end with the suffix s = "23". We want to find out how many numbers in this range are powerful given these constraints.

  1. Initial Setup: We create a depth-first search (dfs) function that will be responsible for constructing and counting powerful numbers. Our suffix s has a length of n = 2. The function is equipped with memoization to avoid repeat calculations.

  2. Subtract 1 from Start: We begin by setting t = "122" (one less than start, which is 123). We call dfs with starting parameters dfs(0, True), meaning we will explore from the first digit without having yet added any digits, and initially, we are bound by the digits in t.

  3. Construction of Powerful Numbers: The dfs function starts constructing numbers and checks at each position if the number can still comply with the suffix and limit. Since we haven't yet reached the length of s (which is 2), it will try adding digits from 0 to the limit for that position, all the while checking if we are still limited by the structure of t.

  4. Suffix Checking: Once the number under construction t reaches the length of s (len(t) - pos == n), the function will check if t ends with s. If lim is False at this point (meaning we're not restricted by start), any number with the suffix s is counted as powerful.

  5. Count: The digits are added, and each complete number going through this process is checked for powerfulness. If it qualifies, the count increases.

  6. Cache Clearing and Finish: After computing the counts up to start - 1, the cache is cleared. Now, t is set to finish which is "130", and then dfs(0, True) is executed for this new value.

Let's walk through the steps of the algorithm with our example inputs:

  • Start by calling dfs for t = "122" with dfs(0, True).
  • The function will consider positions from the first digit to the end, comparing against limit and checking suffix requirements.

For our range, no constructed numbers will have the suffix "23" until we reach the numbers starting with "12".

  • Once we hit "123", we notice it has the suffix "23" and no digit exceeds the limit 3. It will be the first powerful number and thus counted.
  • The most significant digit cannot go beyond "1" (due to t and the limit), but other digits can take all values from "0" to "3". However, no other numbers can end in "23" unless they start with "12".
  • This process continues until dfs finishes checking all numbers up to "122", then the cache is cleared.
  • Next, set t to "130" and repeat dfs with dfs(0, True).
  • Similar to the first run, it will count powerful numbers ("123", "130") up to "130".

Finally, subtract the count from the first run from the second run to find the powerful numbers in the range [start..finish]. In this range, we would get 1 powerful number, which is "123". The "130" is not counted because it doesn't end with "23".

So the result for the input [123, 130, 3, "23"] is 1 powerful number.

Solution Implementation

1from functools import lru_cache
2
3class Solution:
4    def numberOfPowerfulInt(self, start: int, finish: int, limit: int, s: str) -> int:
5        # Cache the results of the recursive calls to avoid redundant calculations
6        @lru_cache(None)
7        def dfs(position: int, is_limited: int):
8            # If the generated number is shorter than the searched term, there are no powerful ints here
9            if len(temp_string) < num_length:
10                return 0
11            # If we reached the end of the temporary number being constructed
12            if len(temp_string) - position == num_length:
13                # If we are limited by the "finish" number, compare substrings
14                return int(s <= temp_string[position:]) if is_limited else 1
15            # Determine the digit limit; if we're not at the limit, we can go up to 9
16            upper_limit = min(int(temp_string[position]) if is_limited else 9, limit)
17            # Initialize counter for powerful integers
18            counter = 0
19            # Recursively calculate counts for all digits up to the upper limit
20            for i in range(upper_limit + 1):
21                counter += dfs(position + 1, is_limited and i == int(temp_string[position]))
22            return counter
23
24        # Get the length of the search term to know when we've built a comparable number
25        num_length = len(s)
26        # Convert start number to a string and subtract 1 to handle inclusive counting
27        temp_string = str(start - 1)
28        # Compute number of powerful integers starting from 'start-1' to set a base
29        count_start = dfs(0, True)
30        # Clear the cache to avoid interference with the next computation
31        dfs.cache_clear()
32        # Convert finish number to a string; this is the actual upper bound
33        temp_string = str(finish)
34        # Compute number of powerful integers up to 'finish'
35        count_finish = dfs(0, True)
36        # Subtract the two counts to get the number of powerful integers in the range
37        return count_finish - count_start
38
1class Solution {
2    private String sequence;    // the sequence of digits to be matched
3    private String threshold;   // the current threshold as a string
4    private Long[] memo;        // a memoization array to store computed values
5    private int digitLimit;     // an upper limit on the digits used in constructing powerful integers
6
7    public long numberOfPowerfulInt(long start, long finish, int limit, String s) {
8        this.sequence = s;
9        this.digitLimit = limit;
10        // Set 'threshold' to one less than 'start' and initialize memoization array
11        threshold = String.valueOf(start - 1);
12        memo = new Long[20];
13        // Compute the number of powerful integers up to just before 'start'
14        long countStart = dfs(0, true);
15        // Now consider integers up to 'finish' for the complete count
16        threshold = String.valueOf(finish);
17        memo = new Long[20];  // reset the memoization array
18        long countFinish = dfs(0, true);
19        // The result is the count from 'start' to 'finish', inclusive
20        return countFinish - countStart;
21    }
22
23    private long dfs(int pos, boolean isLimit) {
24        // If the length of 'threshold' is less than the length of 'sequence', no match is possible
25        if (threshold.length() < sequence.length()) {
26            return 0;
27        }
28        // Base case: if we've reached the length of 'sequence', check if we can include this number
29        if (threshold.length() - pos == sequence.length()) {
30            // If we are not limited, or if 'sequence' is lexicographically not greater than the substring of 'threshold'
31            return isLimit ? (sequence.compareTo(threshold.substring(pos)) <= 0 ? 1 : 0) : 1;
32        }
33        // Decide the upper limit of our next digit (shouldn't exceed 'threshold' if 'isLimit' is true)
34        int upperBound = isLimit ? threshold.charAt(pos) - '0' : 9;
35        upperBound = Math.min(upperBound, digitLimit); // Constrain by 'digitLimit' as well
36        long count = 0;
37        // Loop through all possible digits from 0 to 'upperBound', computing powerful integers
38        for (int i = 0; i <= upperBound; ++i) {
39            // Increment the count recursively, ensuring 'isLimit' is properly passed down
40            count += dfs(pos + 1, isLimit && i == (threshold.charAt(pos) - '0'));
41        }
42        // Memoization: store computed values if we are not bound (this is for optimizing the search space)
43        if (!isLimit) {
44            memo[pos] = count;
45        }
46        return count; // Return the number of powerful integers found at this point
47    }
48}
49
1#include <functional>
2#include <string>
3#include <cstring>
4#include <algorithm>
5
6class Solution {
7public:
8    // Calculate the number of powerful integers within the range [start, finish]
9    // where each digit is less than or equal to `limit` and the number itself is
10    // greater than or equal to the string `s`
11    long long numberOfPowerfulInt(long long start, long long finish, int limit, std::string s) {
12        // Convert 'start - 1' to string and use it as a starting point
13        std::string numStr = std::to_string(start - 1);
14        // Initialize memoization array, which caches results for dynamic programming
15        long long memo[20];
16        std::memset(memo, -1, sizeof(memo));
17
18        // Define recursive function using lambda for depth-first search
19        std::function<long long(int, bool)> dfs = [&](int pos, bool isLimited) -> long long {
20            // If the remaining number length is shorter than s, return 0
21            if (numStr.size() < s.size()) {
22                return 0;
23            }
24            // Use memoization to avoid redundant calculations
25            if (!isLimited && memo[pos] != -1) {
26                return memo[pos];
27            }
28            // If we are at a digit where the total remaining digits match s's length,
29            // only one number can be formed, check if it's valid
30            if (numStr.size() - pos == s.size()) {
31                return isLimited ? s <= numStr.substr(pos) : 1;
32            }
33            long long count = 0;
34            // Determine upper bound for the current digit
35            int upper = std::min(isLimited ? numStr[pos] - '0' : 9, limit);
36            // Explore possible digits at the current position
37            for (int i = 0; i <= upper; ++i) {
38                count += dfs(pos + 1, isLimited && i == (numStr[pos] - '0'));
39            }
40            // Cache the result if it's not limited by a previous digit
41            if (!isLimited) {
42                memo[pos] = count;
43            }
44            return count;
45        };
46
47        // Calculate number of powerful integers up to 'start - 1'
48        long long countStart = dfs(0, true);
49
50        // Update numStr to represent 'finish' and reset memoization
51        numStr = std::to_string(finish);
52        std::memset(memo, -1, sizeof(memo));
53
54        // Calculate number of powerful integers up to 'finish'
55        long long countFinish = dfs(0, true);
56
57        // The result is the difference in counts which gives the powerful ints in range
58        return countFinish - countStart;
59    }
60};
61
1// This function calculates the number of "powerful" integers within a specified range
2// that have a prefix matching a string under a certain limit for each digit.
3function numberOfPowerfulIntegers(start: number, finish: number, limit: number, searchString: string): number {
4    // Convert the (start - 1) to a string to handle the case where start is at the limit
5    let targetString: string = (start - 1).toString();
6  
7    // Initialize a memoization array to store the results for subproblems
8    let memo: number[] = Array(20).fill(-1); 
9
10    // Helper function for depth-first search
11    const dfs = (position: number, isLimit: boolean): number => {
12        // If the target substring is shorter than the search string, return 0
13        if (targetString.length < searchString.length) {
14            return 0;
15        }
16        // If there is no limit and we have computed this subproblem before, return the stored result
17        if (!isLimit && memo[position] !== -1) {
18            return memo[position];
19        }
20        // If the remaining substring matches the length of the search string, check for match
21        if (targetString.length - position === searchString.length) {
22            if (isLimit) {
23                return searchString <= targetString.substring(position) ? 1 : 0;
24            }
25            return 1;
26        }
27
28        let count: number = 0;
29        // Determine the upper bound for this digit; if there's a limit, it's the current digit of targetString
30        const upperBound: number = Math.min(isLimit ? +targetString[position] : 9, limit);
31        // Iterate through all possible digits for this position
32        for (let digit = 0; digit <= upperBound; digit++) {
33            count += dfs(position + 1, isLimit && digit === +targetString[position]);
34        }
35
36        // Memoize the result if there is no limit
37        if (!isLimit) {
38            memo[position] = count;
39        }
40      
41        return count;
42    };
43
44    // Calculate the number of valid integers within the range from 'start' to 't'
45    const countFromStart: number = dfs(0, true);
46    targetString = finish.toString();
47    memo = Array(20).fill(-1); // Reset memoization array
48    const countFromFinish: number = dfs(0, true);
49
50    // The number of "powerful" integers is the difference between the finish and start counts
51    return countFromFinish - countFromStart;
52}
53

Time and Space Complexity

The given Python code defines a method numberOfPowerfulInt that calculates the number of integers in the range [start, finish] where each digit does not exceed the limit and when sorted in non-descending order, the given string s should not come lexicographically after the integers.

To analyze the computational complexity, let us examine the recursive function dfs(pos: int, lim: int):

  • The base case occurs either when the current position pos reaches the length of the temporary string t (subtracted start - 1 or finish), or when the pos is at the distance of n to the end of t. In these cases, the function performs a constant number of operations.
  • The recursive case iterates up to up + 1 times, where up is the minimum between limit and either 9 or the digit at t[pos], depending on the value of lim.
  • The recursion depth is equal to the length of t, which in the worst case will be equal to the number of digits in finish.

Time Complexity

The time complexity is mainly determined by the number of recursive calls. The total number of states is bounded by the product of two factors:

  • The number of positions that we recurse on, which is at most equal to the length of the string representation of finish.
  • The possible values of lim which can either be True or False.

Considering the above, the upper-bound time complexity may be approximated as O(d * 2 * (limit + 1)), where d is the number of digits in the larger number (finish) and the 2 comes from the boolean flag lim. However, due to memoization (@cache), each state is only computed once. Therefore, the time complexity is O(d * (limit + 1)).

Space Complexity

The space complexity comes from the memory used to store recursive calls on the call stack and the cache used by memoization.

  • Call stack: The maximum depth of the recursive call stack is d, the number of digits in finish.
  • Cache: The cache stores results for each unique state of the recursion which, as analyzed above, gives us at most d * 2 * (limit + 1) possible states.

Therefore, the space complexity is O(d * (limit + 1)) because the cache is the dominant factor as it stores an integer for each possible state and boolean flags (lim) are negligible in space compared to the integer storage. The call stack also uses O(d) space, but this is included in the space used by the cache.

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


Fast Track Your Learning with Our Quick Skills Quiz:

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


Recommended Readings


Got a question? Ask the Monster 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.


🪄