Problem Informations

• Problem Index: 2999
• Problem Link: Count the Number of Powerful Integers
• Topics: Math, String, Dynamic Programming

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 (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 \leq \text{start} \leq \text{finish} \leq 10^{15}$
• $1 \leq \text{limit} \leq 9$
• $1 \leq \text{s.length} \leq \lfloor \log_{10}(\text{finish}) \rfloor + 1$
• s only consists of numeric digits which are at most limit.
• s does not have leading zeros.

Intuition

The problem requires us to count integers within a given range [start..finish] that meet two conditions: each digit must be at most limit, and they must end with the suffix s. This suggests a two-part process: generating potential integers based on the limit and matching them against the suffix s. The challenge is to perform this in an efficient manner given the potentially large size of the range.

Approach

The approach to solving this problem involves breaking down the task into manageable steps:

1. String Conversion and Range Adjustment:

   • Convert the boundaries start and finish to string format for easy manipulation of individual digits.
   • Adjust the start by decrementing it to make use of half-open interval logic (start..finish].

2. Calculate Function:

   • Define a helper function calculate that determines, for a given boundary string x, how many powerful integers exist up to x.
   • Compute the powerful integers for both finish and start - 1, and derive the result as the difference between these two values.

3. Suffix and Length Check:

   • Immediately return zero if the length of x is less than that of the suffix s, as x cannot feasibly end in s.
   • If x and s are of equal length, a direct comparison suffices to determine if x is a powerful integer or not.

4. Iterative Digit Check:

   • For cases where x is longer than s, iterate over each digit of x up to the point where s begins (forming the prefix).
   • For each prefix digit, check if it exceeds the limit. If it does, calculate all possible numbers using the permutations of digits from this position onward constrained by limit, and return the count.

5. Prefix Construction and Counting:

   • Construct numbers up to the current digit based on choices allowed by previous digits that haven’t violated the limit, using powers of limit + 1 to account for all possible combinations.
   • When the suffix of x is greater than or equal to s, include this in the count as it means at least one valid number exists where x ends with s under the given constraints.

This structured method of considering digits individually and employing exponential counting for possibilities under limit ensures thorough coverage of all applicable numbers, achieving efficiency necessary for large inputs.

Code

C++

class Solution {
public:
    long long numberOfPowerfulInt(long long start, long long finish, int limit, string s) {
        // Convert the start and finish numbers to strings
        string startStr = to_string(start - 1);
        string finishStr = to_string(finish);
        
        // Calculate the number of powerful integers in the range (start..finish]
        return calculate(finishStr, s, limit) - calculate(startStr, s, limit);
    }

    long long calculate(string x, string s, int limit) {
        // If length of x is less than s, x cannot have s as a suffix
        if (x.length() < s.length()) {
            return 0;
        }
        
        // If x and s have the same length, directly compare them
        if (x.length() == s.length()) {
            return x >= s ? 1 : 0;
        }

        // Extract the suffix of x which has the same length as s
        string suffix = x.substr(x.length() - s.length(), s.length());
        long long count = 0;
        int preLen = x.length() - s.length();

        // Iterate over the prefix part of x
        for (int i = 0; i < preLen; i++) {
            // If any digit exceeds the limit, calculate the possible numbers and exit
            if (limit < (x[i] - '0')) {
                count += static_cast<long>(pow(limit + 1, preLen - i));
                return count;
            }
            
            // Count the numbers that can be formed up to the current digit
            count += static_cast<long>(x[i] - '0') * static_cast<long>(pow(limit + 1, preLen - 1 - i));
        }

        // Add 1 if the suffix of x is greater or equal to s
        if (suffix >= s) {
            count++;
        }

        return count;
    }
};

Python

class Solution:
    def numberOfPowerfulInt(self, start: int, finish: int, limit: int, s: str) -> int:
        # Convert the start and finish numbers to strings
        startStr = str(start - 1)
        finishStr = str(finish)
        
        # Calculate the number of powerful integers in the range (start..finish]
        return self.calculate(finishStr, s, limit) - self.calculate(startStr, s, limit)

    def calculate(self, x: str, s: str, limit: int) -> int:
        # If length of x is less than s, x cannot have s as a suffix
        if len(x) < len(s):
            return 0
        
        # If x and s have the same length, directly compare them
        if len(x) == len(s):
            return 1 if x >= s else 0

        # Extract the suffix of x which has the same length as s
        suffix = x[-len(s):]
        count = 0
        preLen = len(x) - len(s)

        # Iterate over the prefix part of x
        for i in range(preLen):
            # If any digit exceeds the limit, calculate the possible numbers and exit
            if limit < int(x[i]):
                count += (limit + 1) ** (preLen - i)
                return count
            
            # Count the numbers that can be formed up to the current digit
            count += int(x[i]) * (limit + 1) ** (preLen - 1 - i)

        # Add 1 if the suffix of x is greater or equal to s
        if suffix >= s:
            count += 1

        return count

Complexity

• Time complexity: The time complexity of the given code is $O(n)$, where $n$ is the length of the string representation of finish. This is because we are primarily iterating over the string x (representing either start or finish) once. During this iteration, for each character, we perform a constant time operation.

• Space complexity: The space complexity is $O(1)$. The space used by the algorithm is constant and does not depend on the size of the input. This is because all additional space requirements are fixed (e.g., count, suffix) and not dependent on the input size.