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:
- It ends with a given string
s
, which represents a positive integer suffix. - 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:
-
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. -
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 suffixs
.- 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 oft
up to the current position,False
otherwise).
- Parameters of
-
Suffix Checking: Once the length of the number being constructed equals the length of
s
, the function checks ifs
is a suffix of the current number. Iflim
isFalse
, we're not restricted byt
anymore and can increment our count freely. -
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
(iflim
isTrue
, meaning we are still bound by the pre-existing digits oft
) and thelimit
. Then,dfs
recurses for each digit from0
toup
, potentially updatinglim
. -
Computing Counts for Start and Finish: The function
dfs
is called for bothstart - 1
andfinish
. We subtract 1 fromstart
to simplify the computation by including thestart
value in our count. This effectively calculates the total powerful numbers up tostart - 1
and separately up tofinish
, and we get the count in our range[start..finish]
by taking the difference. -
Cache Clearing Between Calls: After calculating the count for
start - 1
, we clear the cache before calculating forfinish
because thelim
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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.
-
Initial Setup: We create a depth-first search (
dfs
) function that will be responsible for constructing and counting powerful numbers. Our suffixs
has a length ofn = 2
. The function is equipped with memoization to avoid repeat calculations. -
Subtract 1 from Start: We begin by setting
t = "122"
(one less thanstart
, which is123
). We calldfs
with starting parametersdfs(0, True)
, meaning we will explore from the first digit without having yet added any digits, and initially, we are bound by the digits int
. -
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 ofs
(which is 2), it will try adding digits from0
to the limit for that position, all the while checking if we are still limited by the structure oft
. -
Suffix Checking: Once the number under construction
t
reaches the length ofs
(len(t) - pos == n
), the function will check ift
ends withs
. Iflim
isFalse
at this point (meaning we're not restricted bystart
), any number with the suffixs
is counted as powerful. -
Count: The digits are added, and each complete number going through this process is checked for powerfulness. If it qualifies, the count increases.
-
Cache Clearing and Finish: After computing the counts up to
start - 1
, the cache is cleared. Now,t
is set tofinish
which is "130", and thendfs(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
fort = "122"
withdfs(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 repeatdfs
withdfs(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 stringt
(subtractedstart - 1
orfinish
), or when thepos
is at the distance ofn
to the end oft
. In these cases, the function performs a constant number of operations. - The recursive case iterates up to
up + 1
times, whereup
is the minimum betweenlimit
and either 9 or the digit att[pos]
, depending on the value oflim
. - The recursion depth is equal to the length of
t
, which in the worst case will be equal to the number of digits infinish
.
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 beTrue
orFalse
.
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 infinish
. - 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.
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)
.
Recommended Readings
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
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 Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we