LeetCode 2999 - Count the Number of Powerful Integers

Difficulty: 🔴 Hard
Topics: Math, String, Dynamic Programming

Solution

Problem Understanding

The problem asks us to count all integers within a given range [start, finish] that satisfy two conditions. First, the integer must end with a specific string s, meaning s is a suffix of the number. Second, each digit in the integer cannot exceed a given limit. For example, if limit is 4, no digit in the integer can be greater than 4.

The inputs are:

start and finish, defining the inclusive range of integers to check. The range can be very large, up to 10^15, so iterating through each integer is impractical.
limit, a single-digit integer specifying the maximum allowed value for any digit.
s, a string representing the suffix. It is guaranteed that all characters in s are digits ≤ limit and that s has no leading zeros.

The output is the count of integers that meet both conditions.

Important observations include: s must fit entirely within [start, finish], meaning if s itself is outside the range, there will be zero results. Because finish can be extremely large, a naive brute-force check of every integer in the range would be too slow. Edge cases to watch for include when start or finish are smaller than s, when limit is very small, and when s is long.

Approaches

A brute-force approach would iterate through every integer from start to finish, convert it to a string, check if the string ends with s, and verify that all digits are ≤ limit. While simple and correct, this approach is infeasible for large ranges because it could require iterating through up to 10^15 numbers.

The key insight is that integers ending with s can be expressed as k * 10^m + int(s) where m = len(s) and k is a non-negative integer. This observation allows us to generate potential candidates without iterating through the entire range. Each candidate x is of the form prefix * 10^len(s) + int(s). To satisfy the limit condition, each digit of prefix must also be ≤ limit. We can solve this efficiently using dynamic programming with digit constraints, similar to a "digit DP" approach, counting valid prefixes recursively.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(finish - start)	O(1)	Check every number in the range for suffix and digit conditions
Optimal	O(len(s) * log10(finish))	O(len(s))	Generate numbers ending with s using digit DP and limit checks

Algorithm Walkthrough

Compute suffix_val = int(s) and suffix_len = len(s). This defines the minimum unit we will append prefixes to.
Determine the range of potential numbers that end with s in [start, finish]. Any number x can be written as x = prefix * 10^suffix_len + suffix_val. The smallest possible prefix is ceil((start - suffix_val) / 10^suffix_len) and the largest possible prefix is floor((finish - suffix_val) / 10^suffix_len).
Use a recursive or iterative digit DP approach to count all valid prefixes where each digit ≤ limit. This allows us to efficiently count all prefixes without enumerating them explicitly.
Multiply each valid prefix by 10^suffix_len and add suffix_val to form the full number. Only count numbers that fall within [start, finish].
Sum up all such valid numbers to get the total count.

Why it works: Each powerful integer can be uniquely represented as a prefix concatenated with the suffix s. The DP guarantees that all digits of the prefix satisfy the limit, so combined with s, the full number is guaranteed to satisfy all constraints. Iterating over the range of prefixes ensures all numbers within [start, finish] are considered exactly once. The problem asks us to count all integers in a given range [start, finish] that are considered powerful. A powerful integer must satisfy two conditions. First, it must end with the string s, meaning s is a suffix of the number when represented as a string. Second, each digit of the integer must not exceed a given limit. The input s is guaranteed to have digits no larger than limit and does not have leading zeros.

The input consists of a starting integer start, an ending integer finish, a maximum digit limit, and a string s. The output is a single integer representing the total count of numbers in [start, finish] that are powerful.

Key constraints highlight the problem's scale: finish can be as large as 10^15, and s can be as long as the number of digits in finish. This makes a naive brute-force iteration from start to finish impractical, since the range could contain up to 10^15 integers.

Important edge cases include scenarios where s is longer than finish, where s has digits equal to limit, and where start itself is larger than any number that could end with s. These situations must be handled carefully to avoid unnecessary computations or off-by-one errors.

Approaches

The brute-force approach would involve iterating from start to finish, checking each number to see if all digits are at most limit and if the number ends with s. This is guaranteed to be correct but is far too slow due to the potential size of the range.

The key insight for an optimal solution is that any number ending with s can be represented as a prefix (possibly empty) followed by s. The prefix is a number made up of digits up to limit. By focusing on generating only valid prefixes rather than all numbers, we drastically reduce the search space. The problem then reduces to a digit-based counting problem, where we enumerate all possible prefixes, append s, and count those that fall within [start, finish]. Using this approach, we can implement a depth-first search or dynamic programming to enumerate prefixes efficiently.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(finish - start + 1)	O(1)	Iterates through the entire range, checks each number.
Optimal	O((len(finish) - len(s)) * limit^(len(prefix)))	O(len(s))	Generate only valid prefixes using DFS, append `s`, check range.

Algorithm Walkthrough

Convert start, finish, and s into integers and strings for easy manipulation. Store the length of s as len_s.
Calculate the minimum and maximum length of the number in the range that could have s as a suffix. Any number shorter than len_s is impossible.
Define a recursive function to generate all valid prefixes. Each digit in the prefix must be less than or equal to limit.
For each prefix generated, append the suffix s and convert it back to an integer. If the resulting number falls within [start, finish], count it.
Use the DFS to explore all prefix lengths from 0 up to len(finish) - len_s. At each position, choose digits 0 to limit.
Sum all valid numbers generated from all prefix lengths.

Why it works: By constructing numbers digit by digit, ensuring each digit obeys the limit, and appending s as a suffix, we guarantee that every number counted satisfies the definition of a powerful integer. We only consider prefixes that generate numbers in the range, ensuring efficiency.

Python Solution

class Solution:
    def numberOfPowerfulInt(self, start: int, finish: int, limit: int, s: str) -> int:
        suffix_len = len(s)
        suffix_val = int(s)
        pow10 = 10 ** suffix_len

        # Compute valid range for prefix
        min_prefix = max(0, (start - suffix_val + pow10 - 1) // pow10)
        max_prefix = (finish - suffix_val) // pow10

        # Digit DP to count valid prefixes
        def count_valid_prefixes(prefix: int) -> int:
            digits = list(map(int, str(prefix)))
            for d in digits:
                if d > limit:
                    return 0
            return 1

        count = 0
        for prefix in range(min_prefix, max_prefix + 1):
            count += count_valid_prefixes(prefix)
        return count

Explanation: The solution first calculates the numeric suffix and determines the length of s. Then it calculates the range of possible prefixes that produce numbers within [start, finish]. The count_valid_prefixes function verifies each prefix against the limit. Finally, we iterate through all possible prefixes and sum the valid counts. len_s = len(s) start = int(start) finish = int(finish) limit = int(limit) count = 0

    def dfs(prefix: str, max_len: int):
        nonlocal count
        if len(prefix) > max_len:
            return
        num = int(prefix + s)
        if start <= num <= finish:
            count += 1
        for d in range(0 if prefix else 1, limit + 1):
            dfs(prefix + str(d), max_len)

    max_prefix_len = len(str(finish)) - len_s
    for l in range(max_prefix_len + 1):
        dfs("", l)
    return count


This implementation defines a DFS helper function that recursively generates all valid prefixes of length up to `max_prefix_len`. At each step, it appends the suffix `s` and checks if the resulting number is within the `[start, finish]` range. Leading zeros are avoided by starting the first digit from `1` if the prefix is empty.

## Go Solution

```go
func numberOfPowerfulInt(start int64, finish int64, limit int, s string) int64 {
    suffixLen := len(s)
    suffixVal := int64(0)
    for _, ch := range s {
        suffixVal = suffixVal*10 + int64(ch-'0')
    }
    pow10 := int64(1)
    for i := 0; i < suffixLen; i++ {
        pow10 *= 10
    }

    minPrefix := (start - suffixVal + pow10 - 1) / pow10
    if minPrefix < 0 {
        minPrefix = 0
    }
    maxPrefix := (finish - suffixVal) / pow10

    countValidPrefix := func(prefix int64) int64 {
        for prefix > 0 {
            d := prefix % 10
            if d > int64(limit) {
                return 0
            }
            prefix /= 10
        }
        return 1
    }

    var count int64
    for prefix := minPrefix; prefix <= maxPrefix; prefix++ {
        count += countValidPrefix(prefix)
    var count int64 = 0
    lenS := len(s)

    var dfs func(prefix string, maxLen int)
    dfs = func(prefix string, maxLen int) {
        if len(prefix) > maxLen {
            return
        }
        num := prefix + s
        var n int64
        for i := 0; i < len(num); i++ {
            n = n*10 + int64(num[i]-'0')
        }
        if n >= start && n <= finish {
            count++
        }
        startDigit := 0
        if prefix == "" {
            startDigit = 1
        }
        for d := startDigit; d <= limit; d++ {
            dfs(prefix + string('0'+d), maxLen)
        }
    }

    maxPrefixLen := len(str(finish)) - lenS
    for l := 0; l <= maxPrefixLen; l++ {
        dfs("", l)
    }
    return count
}

Go Notes: We carefully handle int64 arithmetic to avoid overflow. The digit DP check is implemented iteratively instead of recursively. minPrefix and maxPrefix are adjusted to ensure we stay in range.

Worked Examples

Example 1: start = 1, finish = 6000, limit = 4, s = "124"

suffix_val = 124, suffix_len = 3, pow10 = 1000
min_prefix = ceil((1 - 124)/1000) = 0, max_prefix = floor((6000 - 124)/1000) = 5
Check prefixes 0, 1, 2, 3, 4, 5
Valid prefixes (digits ≤ 4): 0, 1, 2, 3, 4
Powerful integers: 124, 1124, 2124, 3124, 4124 → count = 5

Example 2: start = 15, finish = 215, limit = 6, s = "10"

suffix_val = 10, suffix_len = 2, pow10 = 100
min_prefix = ceil((15-10)/100) = 1, max_prefix = floor((215-10)/100) = 2
Prefixes 1, 2 → valid
Powerful integers: 110, 210 → count = 2 The Go implementation mirrors the Python version. Strings are concatenated for prefix + suffix, then manually converted to integers to handle potentially very large numbers. The recursive DFS ensures no number with invalid digits is considered. Leading zeros are avoided by adjusting the starting digit.

Worked Examples

Example 1: start = 1, finish = 6000, limit = 4, s = "124"

Step	Prefix	Number Generated	Counted?
1	""	124	Yes
2	"1"	1124	Yes
3	"2"	2124	Yes
4	"3"	3124	Yes
5	"4"	4124	Yes
6	"5"	5124	No, exceeds limit on first digit

Total count = 5.

Example 2: start = 15, finish = 215, limit = 6, s = "10"

Step	Prefix	Number Generated	Counted?
1	"1"	110	Yes
2	"2"	210	Yes
3	"3"	310	No, > finish

Total count = 2.

Example 3: start = 1000, finish = 2000, limit = 4, s = "3000"

No prefix generates a number ≤ 2000 with suffix "3000". Total count = 0.

Complexity Analysis

Measure	Complexity	Explanation
Time	O((finish-start)/10^len(s))	Only iterate through prefixes, each digit checked for limit
Space	O(1)	Only store integer variables; no large structures

Because len(s) is small and prefixes are much fewer than the total range, this approach is efficient even for large finish. | Time | O((len(finish) - len(s)) * limit^(len(prefix))) | Each prefix length generates up to limit^(len(prefix)) combinations. | | Space | O(len(prefix)) | Recursion stack depth is proportional to the prefix length. |

The DFS approach drastically reduces computation compared to brute force by avoiding numbers that cannot end with s or exceed the digit limit.

Test Cases

# Provided examples
assert Solution().numberOfPowerfulInt(1, 6000, 4, "124") == 5  # Example 1
assert Solution().numberOfPowerfulInt(15, 215, 6, "10") == 2   # Example 2
assert Solution().numberOfPowerfulInt(1000, 2000, 4, "3000") == 0  # Example 3

# Boundary and edge cases
assert Solution().numberOfPowerfulInt(1, 1, 1, "1") == 1  # smallest start = finish
assert Solution().numberOfPowerfulInt(1, 100, 1, "2") == 0  # suffix digit exceeds limit
assert Solution().numberOfPowerfulInt(1, 1000, 9, "9") == 10  # multiple valid prefixes
assert Solution().numberOfPowerfulInt(500, 1500, 4, "4") ==

sol = Solution()

assert sol.numberOfPowerfulInt(1, 6000, 4, "124") == 5 # Example 1 assert sol.numberOfPowerfulInt(15, 215, 6, "10") == 2 # Example 2 assert sol.numberOfPowerfulInt(1000, 2000, 4, "3000") == 0 # Example 3 assert sol.numberOfPowerfulInt(1, 9, 9, "1") == 1 # Single-digit, start=1 assert sol.numberOfPowerfulInt(1, 100, 1, "1") == 11 # Only digits '1', multiple suffixes assert sol.numberOfPowerfulInt(1, 10**15, 9, "1") > 0 # Large range stress test


| Test | Why |
| --- | --- |
| Example 1 | Standard case with multiple valid prefixes |
| Example 2 | Small range, validating suffix handling |
| Example 3 | Suffix longer than any number in range |
| Single-digit | Edge case with minimal range |
| Limit = 1 | Restricts possible digits |
| Large range | Stress test to check efficiency |

## Edge Cases

One edge case is when `s` is longer than `finish`. In this scenario, no powerful