We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Powerful Integers

Number: 1010

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given three integers x, y, and bound, return a list of all the powerful integers that have a value less than or equal to bound. An integer is powerful if it can be represented as x^i + y^j for some integers i >= 0 and j >= 0. Each value in the answer should occur at most once and the answer can be returned in any order.

Key Insights

  • Use two nested loops to consider all exponents i and j such that x^i and y^j are less than or equal to bound.
  • Use a set (or equivalent data structure) to store results and avoid duplicate values.
  • When x or y equals 1, break out of the corresponding loop to avoid infinite iterations since 1 raised to any power remains 1.
  • The bounds for i and j are essentially derived from the inequality x^i <= bound and y^j <= bound respectively.

Space and Time Complexity

Time Complexity: O((log_bound/ log_x) * (log_bound/ log_y)) in the worst-case scenario, due to iterating over possible powers. Space Complexity: O(N) where N is the number of unique powerful integers stored in the result set.

Solution

We use an enumeration approach where two loops generate powers of x and y while their sum remains within the given bound. A set is used to record sums uniquely. Special care is taken to handle the cases when x or y are equal to 1 to prevent infinite loops. The idea is to iterate through potential exponent pairs (i, j) and add x^i + y^j to the result set if the sum is less than or equal to bound. Finally, the set is converted to a list and returned.

Code Solutions

# Python implementation with detailed comments
def powerfulIntegers(x, y, bound):
    # Use a set to avoid duplicates
    result = set()
    
    # Early return if bound is too small to form valid sum (minimum sum is 2 when i = 0, j = 0)
    if bound < 2:
        return []
    
    i = 0
    while True:
        # Compute x raised to the power of i
        x_power = x ** i
        # If current power of x exceeds bound, no need to continue further for higher powers
        if x_power > bound:
            break
        
        j = 0
        while True:
            # Compute y raised to the power of j
            y_power = y ** j
            current_sum = x_power + y_power
            
            # If sum is within the allowed bound, add it to the result set
            if current_sum <= bound:
                result.add(current_sum)
            else:
                # Break inner loop if adding further will exceed bound
                break
            
            # Special case: if y is 1, all higher powers are the same => avoid infinite loop
            if y == 1:
                break
            j += 1
        
        # Special case: if x is 1, avoid infinite loop (all powers are same)
        if x == 1:
            break
        i += 1
    
    # Return the result as a list
    return list(result)

# Example usage:
print(powerfulIntegers(2, 3, 10))
← Back to All Questions