Count the Number of Powerful Integers — LeetCode 2999 Python Solution

The problem

You are given three integers start, finish, and limit. You are also given a 0-indexed string s representing a positive integer.

Example

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.

Python solution

class Solution:
    def numberOfPowerfulInt(self, start: int, finish: int, limit: int, s: str) -> int:
        @cache
        def dfs(pos: int, lim: int) -> int:
            if len(t) < n:
                return 0
            if len(t) - pos == n:
                return int(s <= t[pos:]) if lim else 1
            up = min(int(t[pos]) if lim else 9, limit)
            ans = 0
            for i in range(up + 1):
                ans += dfs(pos + 1, lim and i == int(t[pos]))
            return ans

        n = len(s)
        t = str(start - 1)
        a = dfs(0, True)
        dfs.cache_clear()
        t = str(finish)
        b = dfs(0, True)
        return b - a

Complexity

Pattern: Dynamic Programming

Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 2999. Count the Number of Powerful Integers is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming.

The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.

Related problems