Count the Number of Powerful Integers

HARD

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 <= start <= finish <= 10¹⁵
1 <= limit <= 9
1 <= s.length <= floor(log₁₀(finish)) + 1
s only consists of numeric digits which are at most limit.
s does not have leading zeros.

Approaches

Checkout 2 different approaches to solve Count the Number of Powerful Integers. Click on different approaches to view the approach and algorithm in detail.

Brute Force Iteration

This approach involves a straightforward iteration through every integer in the given range [start, finish]. For each integer, it performs checks to determine if it qualifies as a 'powerful integer' based on the two specified conditions: having s as a suffix and all its digits being within the limit.

Algorithm

Initialize a counter powerful_count to 0.
Iterate through each integer x from start to finish.
For each integer x, check if it is a powerful integer:
- Convert x to its string representation, x_str.
- Suffix Check: Verify if x_str ends with the given suffix string s.
- Digit Limit Check: If the suffix check passes, iterate through each character (digit) of x_str. If any digit is greater than limit, the number is not powerful.
If x satisfies both conditions, increment powerful_count.
After the loop finishes, return powerful_count.

The brute-force method directly translates the problem definition into code. It uses a loop that runs from start to finish. Inside the loop, each number is tested.

To test a number i, we first check the suffix condition. This is easily done by converting both the number i and the suffix s into strings and using the endsWith string method.

If the suffix condition is met, we proceed to the second condition: the digit limit. We can iterate through the digits of i (either by using modulo and division arithmetic or by iterating through its string representation) and check if each digit is less than or equal to limit.

If a number successfully passes both checks, we increment a counter. The final value of this counter is the result.

class Solution {
    public long numberOfPowerfulInt(long start, long finish, int limit, String s) {
        long count = 0;
        for (long i = start; i <= finish; i++) {
            if (isPowerful(i, limit, s)) {
                count++;
            }
        }
        return count;
    }

    private boolean isPowerful(long num, int limit, String s) {
        String numStr = String.valueOf(num);
        
        // 1. Suffix check
        if (!numStr.endsWith(s)) {
            return false;
        }
        
        // 2. Digit limit check
        for (char c : numStr.toCharArray()) {
            if ((c - '0') > limit) {
                return false;
            }
        }
        
        return true;
    }
}

While simple, this approach is not feasible for the given constraints where finish can be up to 10^15.

Complexity Analysis

Time Complexity: O((finish - start) * log10(finish))Space Complexity: O(log10(finish))

Pros and Cons

Pros:

Simple to understand and implement.
Correct for small ranges.

Cons:

Extremely inefficient for large ranges, leading to a 'Time Limit Exceeded' error on most platforms for the given constraints.

Code Solutions

Checking out 4 solutions in different languages for Count the Number of Powerful Integers. Click on different languages to view the code.

public class Solution { private string s ; private string t ; private long ?[] f ; private int limit ; public long NumberOfPowerfulInt ( long start , long finish , int limit , string s ) { this . s = s ; this . limit = limit ; t = ( start - 1 ). ToString (); f = new long ?[ 20 ]; long a = Dfs ( 0 , true ); t = finish . ToString (); f = new long ?[ 20 ]; long b = Dfs ( 0 , true ); return b - a ; } private long Dfs ( int pos , bool lim ) { if ( t . Length < s . Length ) { return 0 ; } if (! lim && f [ pos ]. HasValue ) { return f [ pos ]. Value ; } if ( t . Length - pos == s . Length ) { return lim ? ( string . Compare ( s , t . Substring ( pos )) <= 0 ? 1 : 0 ) : 1 ; } int up = lim ? t [ pos ] - '0' : 9 ; up = Math . Min ( up , limit ); long ans = 0 ; for ( int i = 0 ; i <= up ; ++ i ) { ans += Dfs ( pos + 1 , lim && i == ( t [ pos ] - '0' )); } if (! lim ) { f [ pos ] = ans ; } return ans ; } }

Video Solution

Watch the video walkthrough for Count the Number of Powerful Integers

Patterns:

MathDynamic Programming

Data Structures:

String

Companies:

HashedIn |Sprinklr |