You are given three integers start, finish, and limit. You are also given a 0-indexed string s representing a positive integer.
A positive integer x is called powerful if it ends with s (in other words, s is a suffix of x) and each digit in x is at most limit.
Return the total number of powerful integers in the range [start..finish].
A string x is a suffix of a string y if and only if x is a substring of y that starts from some index (including 0) in y and extends to the index y.length - 1. For example, 25 is a suffix of 5125 whereas 512 is not.
Example 1:
Input: start = 1, finish = 6000, limit = 4, s = "124" Output: 5 Explanation: The powerful integers in the range [1..6000] are 124, 1124, 2124, 3124, and, 4124. All these integers have each digit <= 4, and "124" as a suffix. Note that 5124 is not a powerful integer because the first digit is 5 which is greater than 4. It can be shown that there are only 5 powerful integers in this range.
Example 2:
Input: start = 15, finish = 215, limit = 6, s = "10" Output: 2 Explanation: The powerful integers in the range [15..215] are 110 and 210. All these integers have each digit <= 6, and "10" as a suffix. It can be shown that there are only 2 powerful integers in this range.
Example 3:
Input: start = 1000, finish = 2000, limit = 4, s = "3000" Output: 0 Explanation: All integers in the range [1000..2000] are smaller than 3000, hence "3000" cannot be a suffix of any integer in this range.
Constraints:
1 <= start <= finish <= 10151 <= limit <= 91 <= s.length <= floor(log10(finish)) + 1s only consists of numeric digits which are at most limit.s does not have leading zeros.Problem Overview: You are given a range [start, finish], a digit limit, and a string s. A number is considered powerful if every digit is ≤ limit and the number ends with the suffix s. The task is to count how many such integers exist inside the range.
Approach 1: Brute Force Generation (O(n * d) time, O(1) space)
The most direct approach iterates through every number between start and finish. Convert each number to a string, check whether it ends with s, and verify that every digit is ≤ limit. The suffix comparison is a simple string operation, while the digit validation scans each character. This method works for small ranges but becomes infeasible when the interval spans millions or billions of numbers.
An alternative brute force variation generates numbers digit by digit where each digit is ≤ limit, then filters those ending with s and inside the range. Both variants still explore too many candidates when the bounds are large.
Approach 2: Mathematical Construction / Digit DP (O(d) time, O(d) space)
The key observation: every valid number must end with the fixed suffix s. Instead of scanning the entire range, treat the number as prefix + s. Only the prefix digits vary, and every digit in the prefix must also be ≤ limit. The problem reduces to counting valid prefixes such that the full number lies within [start, finish].
Convert the bounds into strings and compute how many prefixes produce numbers ≤ a given bound. This is a classic dynamic programming over digits problem. At each position, decide which digit (0…limit) can be placed while respecting the tight constraint of the bound. The suffix is fixed, so the DP only processes the prefix portion.
To get the final result, compute count(finish) - count(start - 1). Each count(x) counts valid numbers ≤ x. The DP ensures digits never exceed the limit and the constructed number always ends with s. This approach avoids enumerating the range and runs in time proportional to the number of digits.
The logic combines ideas from math and digit constraints with suffix matching from string handling. The result is efficient even when the numeric range is extremely large.
Recommended for interviews: The mathematical construction with digit DP is the expected solution. Brute force demonstrates understanding of the constraints, but the DP approach shows that you can transform the range problem into a prefix-counting problem and handle digit constraints efficiently.
This approach involves generating numbers by appending different prefixes to 's', checking if they're powerful numbers within the specified range. We start by generating the smallest number that ends with 's' and continue checking larger numbers by incrementally adding allowed digits as prefixes. We'll ensure each prefix leads to a number < or = finish and continues applying constraints until finish is no longer reachable with valid digits.
The C implementation uses basic string operations to verify if a number is powerful. It checks for the suffix match and ensures each digit is within the limit. The main function calculates the count by iterating through the range [start, finish].
Time Complexity: O(n * m) where n is the number of elements in the range and m is the length of each number in digits.
Space Complexity: O(1)
This alternative approach leverages carefully constructing numbers using suffix 's' with digits 0 to limit appended as prefixes. We eliminate numbers not in range by direct construction, reducing iteration. This requires potential backtracking to build valid numbers and avoid unnecessary calculations.
The detailed explanation of C implementation, describing direct construction of numbers without iterating through the entire range for efficiency.
Time Complexity: Reduced compared to brute force due to targeted number constructions.
Space Complexity: O(1)
This problem is essentially about finding the count of numbers in the given range [l, .., r] that satisfy the conditions. The count depends on the number of digits and the value of each digit. We can solve this problem using the Digit DP approach, where the size of the number has minimal impact on the complexity.
For the range [l, .., r], we typically transform it into two subproblems: [1, .., r] and [1, .., l - 1], i.e.,
$
ans = sum_{i=1}^{r} ans_i - sum_{i=1}^{l-1} ans_i
For this problem, we calculate the count of numbers in [1, finish] that satisfy the conditions, and subtract the count of numbers in [1, start - 1] that satisfy the conditions to get the final answer.
We use memoization to implement Digit DP. Starting from the topmost digit, we recursively calculate the number of valid numbers, accumulate the results layer by layer, and finally return the answer from the starting point.
The basic steps are as follows:
and finish to strings for easier manipulation in Digit DP., which represents the count of valid numbers starting from the pos-th digit, with the current restriction condition lim., return 0., check if the current number satisfies the condition and return 1 or 0.. Then iterate through the digits i from 0 to up, recursively call dfs(pos + 1, lim \&\& i == t[pos]), and accumulate the results. is false, store the current result in the cache to avoid redundant calculations.The answer is the count of valid numbers in [1, finish] minus the count of valid numbers in [1, start - 1].
Time complexity is O(log M times D), and space complexity is O(log M), where M is the upper limit of the number, and D = 10$.
| Approach | Complexity |
|---|---|
| Brute Force Generation | Time Complexity: O(n * m) where n is the number of elements in the range and m is the length of each number in digits. |
| Mathematical Construction | Time Complexity: Reduced compared to brute force due to targeted number constructions. |
| Digit DP | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Range Iteration | O(n * d) | O(1) | Small numeric ranges where iterating every number is feasible |
| Digit Generation with Validation | O(k * d) | O(d) | When generating candidate numbers with digit constraints before filtering |
| Mathematical Construction / Digit DP | O(d) | O(d) | Large ranges where counting valid prefixes is far more efficient than enumeration |
Count the Number of Powerful Integers | Detailed Thought Process | Leetcode 2999 | codestorywithMIK • codestorywithMIK • 13,027 views views
Watch 9 more video solutions →Practice Count the Number of Powerful Integers with our built-in code editor and test cases.
Practice on FleetCode