Count the Number of Powerful Integers

Problem Description

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 and each digit in x is at most limit. Return the total number of powerful integers in the range [start..finish].

Key Insights

• A powerful integer must end with the string s.
• Each digit of the integer must be less than or equal to limit.
• The maximum length of the integers in the range is determined by the length of s and the constraints of start and finish.
• The problem requires checking integers that can be formed by appending digits (0 to limit) in front of s.

Space and Time Complexity

Time Complexity: O(limit^length of s) - where length of s is the number of digits that can be added before s. Space Complexity: O(1) - since we are using a constant amount of space to store variables.

Solution

To solve the problem, we can iterate through all possible prefixes that can be added to the string s such that the resulting integer is in the given range. We will check each constructed integer to see if it is within the range [start, finish] and if all its digits are less than or equal to the limit. We can use a recursive or iterative approach to build the prefixes.

1. Start by generating possible integers by appending digits 0 to limit to the left of s.
2. Convert the constructed string to an integer and check if it lies within the specified range.
3. Count the integers that meet the criteria.

Code Solutions