Count the Number of Powerful Integers

Hard

Google

2 views

Topics:

Dynamic ProgrammingRecursion

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^15
1 <= limit <= 9
1 <= s.length <= floor(log10(finish)) + 1
s only consists of numeric digits which are at most limit.
s does not have leading zeros.

Count the Number of Powerful Integers

Hard

Google

2 views

Topics:

Dynamic ProgrammingRecursion

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^15
1 <= limit <= 9
1 <= s.length <= floor(log10(finish)) + 1
s only consists of numeric digits which are at most limit.
s does not have leading zeros.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the values of `start`, `finish`, and `limit`? Are they positive integers?
Can `start` or `finish` be zero?
Can `start` be greater than `finish`?
Is the definition of 'powerful integer' inclusive of `finish`? That is, should I count `finish` if it meets the criteria?
By 'number of powerful integers', do you mean the count of integers or something else?

Brute Force Solution

Approach

To find the number of powerful integers, the brute force approach involves checking every possible integer within a specific range. For each number, we determine if it meets the specified conditions to be considered a powerful integer. This method guarantees finding all valid numbers by exhaustively testing all candidates.

Here's how the algorithm would work step-by-step:

Start by considering the smallest number within the given range.
Check if this number ends with the given suffix.
If it does, determine if adding the given start to the beginning of the suffix results in a number less than or equal to the upper limit.
If the number from the previous step is within the bound, count this as a powerful integer.
Now, move to the next number and repeat steps 2-4.
Continue this process until you reach the largest number within the specified range.
The total count of numbers that satisfied the criteria represents the number of powerful integers.

Code Implementation

def count_powerful_integers_brute_force(start, finish, suffix):
    suffix_length = len(str(suffix))
    count = 0

    # Iterate through all numbers in the given range
    for current_number in range(start, finish + 1):
        current_number_string = str(current_number)

        # Check if the number ends with the given suffix
        if current_number_string.endswith(str(suffix)):
            
            # Construct potential powerful integer by prepending start to the suffix
            potential_powerful_integer = int(str(start) + current_number_string[suffix_length:])
            
            # Ensure the constructed integer is within the upper bound
            if potential_powerful_integer <= finish:
                count += 1

    return count

Big(O) Analysis

Time Complexity

O(upper_bound - lower_bound) – The brute force approach iterates through every number within the range defined by the lower and upper bounds. For each number, a constant amount of work is done to check if it's a powerful integer, involving suffix matching and bound checking. Thus, the time complexity is directly proportional to the number of integers within the given range. Therefore, the time complexity is O(upper_bound - lower_bound), where upper_bound and lower_bound represent the upper and lower limits of the range, respectively. It simplifies to O(n) where n represents the range of numbers being checked.

Space Complexity

O(1) – The brute force approach iterates through numbers within the given range, checking each one against the provided criteria. This solution doesn't create any auxiliary data structures like arrays, hash maps, or trees to store intermediate results or visited numbers. It only uses a few constant space variables to hold the current number being examined and potentially a counter for powerful integers. Therefore, the space complexity remains constant regardless of the size of the input range.

Optimal Solution

Approach

The key to solving this problem efficiently is to avoid checking every single number. We need a smart way to count the powerful integers by analyzing their structure and using math to reduce the calculations.

Here's how the algorithm would work step-by-step:

First, consider the upper limit of the range. We need to figure out how many powerful integers are less than or equal to it.
Then, consider the lower limit of the range. We need to figure out how many powerful integers are strictly less than it.
The difference between the two counts will give us the total number of powerful integers within the given range (inclusive).
To count powerful integers efficiently, break down the number into its prefix (the beginning part) and consider the constraint involving the suffix.
Think about how different prefixes can lead to a powerful integer when combined with the required suffix.
Instead of constructing and checking each potential number, compute how many numbers with that prefix would satisfy the conditions.
When the prefix matches part of either the upper or lower bound of our range, adjust our calculations to make sure we don't over-count or under-count the powerful integers.

Code Implementation

def count_powerful_integers(start, finish, power, suffix):
    def count_less_or_equal(limit, power_value, suffix_value):
        limit_string = str(limit)
        suffix_string = str(suffix_value)
        suffix_length = len(suffix_string)
        result = 0
        prefix_length = len(limit_string) - suffix_length

        for prefix_digits in range(1, prefix_length + 1):
            # Count all numbers with shorter prefixes.
            count = 9 ** (prefix_length - prefix_digits)
            if prefix_digits > 1:
                result += (9 * count)
            else:
                result += count

        prefix = limit_string[:prefix_length]

        for prefix_digits_count in range(1, len(prefix) + 1):

            if prefix_digits_count < len(prefix):
                prefix_value = int(prefix[:prefix_digits_count])

                if prefix_digits_count > 1:
                    result += prefix_value * (power_value**(prefix_length - prefix_digits_count))
                else:
                    result += (prefix_value - 1) * (power_value**(prefix_length - prefix_digits_count))
            else:
                prefix_value = int(prefix)

                powerful_number = int(str(prefix_value) + suffix_string)

                if powerful_number <= limit:
                    result += 1

        return result

    # Subtract the count of powerful integers less than the start value.
    start_minus_one = start - 1

    result = count_less_or_equal(finish, power, suffix) - count_less_or_equal(start_minus_one, power, suffix)

    return result

Big(O) Analysis

Time Complexity

O(log(bound)) – The algorithm's runtime is primarily determined by the number of digits in the upper bound of the range. We iterate through potential prefixes, which correspond to the digits of the upper bound. The number of iterations grows logarithmically with the upper bound since the number of digits in a number grows logarithmically with the number itself. Therefore, the time complexity is O(log(bound)), where bound represents the maximum value of the upper and lower bounds.

Space Complexity

O(1) – The described solution primarily focuses on mathematical calculations and analysis of number prefixes. No auxiliary data structures like arrays, hash maps, or significant recursion are mentioned or implied. Therefore, the algorithm uses a constant amount of extra space, independent of the size of the input numbers (range limits).

Edge Cases

Case	How to Handle
Low bound is greater than high bound	Return 0 immediately as no numbers within range exist.
Single digit suffix is 0	Count is simply 1 (the suffix itself if within bounds).
Suffix is longer than low or high bound	The generated number will be larger than the bound; handle appropriately in counting.
Prefix equals to zero after subtracting the suffix.	Ensure no leading zeros are added to the new integer when constructing numbers.
Base is zero, and suffix is zero	Count numbers from zero to max number that fits the bound condition.
Base is very large, causing near integer overflow	Utilize appropriate data types (e.g., long) and check intermediate calculations for overflows.
Low and high bounds are equal to the suffix	The result is 1 when low is equal to high and equal to the suffix, otherwise 0.
Suffix contains leading zeros, although that is disallowed in an integer	The provided suffix itself is invalid input, which can be addressed through input validation by returning zero.