LeetCode Solutions Blog

Count the Number of Powerful Integers

Number: 3243

Difficulty: Hard

Paid? No

Companies: Sprinklr

Problem Description

Given three integers start, finish, and limit, and a 0-indexed string s representing a positive integer, count how many powerful integers x in the interval [start, finish] exist such that:

x ends with s (s is a suffix of x).
Every digit in x is at most limit. Note that s has no leading zeros and its digits are all at most limit.

Internally, any such x can be written as: x = k * 10^(|s|) + offset , where offset = integer value of s. The problem then reduces to finding all values k for which: start ≤ k * 10^(|s|) + offset ≤ finish and the digits of both k (when written normally) and s are ≤ limit.

Key Insights

Express every candidate integer x in the form k * 10^(|s|) + offset; this isolates the suffix.
Compute the valid k-range from the inequality: start ≤ k * base + offset ≤ finish.
The condition “each digit is at most limit” must hold for both s (given) and the prefix k; therefore, count only those k (within the computed range) whose decimal digits are all among 0, 1, …, limit.
For limit = 9, since all digits are valid, the problem reduces to counting the number of integers in the k-range.
For other values of limit, use a digit DP (dynamic programming) approach to count the numbers in a range satisfying the digit constraint.

Space and Time Complexity

Time Complexity: O(D * 2 * 2) per DP call where D is the maximum number of digits in k_max (at most 15). Counting valid k in the range uses two DP calls. Space Complexity: O(D * 2 * 2) for memoization in the DP. Note: Since the maximum number of digits is small, the DP approach is efficient.

Solution

We first determine: base = 10^(|s|) offset = integer value of s Then, we solve for k in the inequality: start ≤ k * base + offset ≤ finish ⇒ k ∈ [ceil((start - offset) / base), floor((finish - offset) / base)] Let k_low and k_high be the bounds (adjusting k_low to at least 0). We then need to count, among all k in [k_low, k_high], those whose decimal representation has each digit ≤ limit.

When limit equals 9, no extra filtering is needed. For other cases, we use a digit DP counting function that given an integer N returns how many numbers in [0, N] are “digit-limited” (each digit is in [0, limit]). Using this function, the answer is: dp(k_high) - dp(k_low - 1) This approach uses a DP that iterates over the digits of N and at each step considers digits allowed by the limit, taking into account whether we are still “tight” with N and whether we have started the number (to handle leading zeros properly).

Code Solutions

# Python solution for counting powerful integers

def powerfulIntegers(start: int, finish: int, limit: int, s: str) -> int:
    # Helper: count numbers in [0, N] that have each digit <= limit
    def count_valid(N: int, limit: int) -> int:
        # Convert N to string for digit DP
        digits = list(map(int, str(N)))
        n = len(digits)
        from functools import lru_cache

        @lru_cache(maxsize=None)
        def dp(pos: int, tight: bool, leading: bool) -> int:
            # base case: processed all digits
            if pos == n:
                # if number has been started, count as valid; otherwise, count 0 (or count 0 as valid if we consider the number 0)
                return 0 if leading else 1
            res = 0
            # determine the maximum digit allowed at this position due to the tight constraint
            max_digit = digits[pos] if tight else 9
            for d in range(0, max_digit + 1):
                # If d is greater than limit and we are in the number (non-leading), skip
                if (not leading or d > 0) and d > limit:
                    continue
                new_leading = leading and (d == 0)
                new_tight = tight and (d == max_digit)
                res += dp(pos + 1, new_tight, new_leading)
            return res

        return dp(0, True, True) + (1 if N >= 0 else 0)

    # Calculate base and offset from suffix s
    base = 10 ** len(s)
    offset = int(s)
    
    # Determine valid k range such that: k * base + offset in [start, finish]
    # Use ceiling division for lower bound; adjust if necessary.
    def ceil_div(a: int, b: int) -> int:
        return -((-a) // b)
    
    k_low = ceil_div(start - offset, base)
    k_high = (finish - offset) // base

    # k must be at least 0 because it represents the prefix (even if it is 0)
    k_low = max(k_low, 0)
    
    # If no k exists in the range, return 0
    if k_low > k_high:
        return 0

    # For limit 9, all digits [0-9] are allowed, so count is simply the range size.
    if limit == 9:
        return k_high - k_low + 1

    # Otherwise, count valid k using digit DP in the range [k_low, k_high]
    # dp_count(n) counts numbers in [0, n] with allowed digits
    def dp_count(n: int) -> int:
        return count_valid(n, limit)
    
    # If k_low is 0, dp_count(-1) should be 0.
    lower_count = dp_count(k_low - 1) if k_low > 0 else 0
    total = dp_count(k_high) - lower_count
    return total


# Example usage:
if __name__ == "__main__":
    # Example 1
    start = 1
    finish = 6000
    limit = 4
    s = "124"
    print(powerfulIntegers(start, finish, limit, s))  # Expected output: 5