Powerful Integers - Leetcode Solution

Problem statement: Given two positive integers x and y, an integer is powerful if it is equal to x^i + y^j for some integers i >= 0 and j >= 0. Return a list of all powerful integers that have value less than or equal to bound.

Input:

• Two positive integers x and y
• An integer bound, that is the maximum value of an integer that could be considered a powerful integer.

Output:

• A list of all powerful integers that are less than or equal to the given bound.

Approach: One way to solve the problem is to generate all possible pairs of i and j values such that x^i + y^j is less than or equal to bound. For generating i and j values, we can use nested loops. We can stop the outer loop when x^i is greater than the bound as any further increase in i will result in a value that is greater than the bound. Similarly, we can stop the inner loop when y^j is greater than the bound.

To avoid generating duplicate values, we need to use a set to store the powerful integers. Finally, we can convert the set to a list and return the result.

Code:

def powerfulIntegers(x: int, y: int, bound: int) -> List[int]:
    powerful_integers = set()
    for i in range(20):
        for j in range(20):
            num = x**i + y**j
            if num <= bound:
                powerful_integers.add(num)
            else:
                break
            if y == 1:
                break
        if x == 1:
            break
    return list(powerful_integers)

In the above code, we are generating up to 20 values for both 'i' and 'j' as any value beyond that will be very large and will not satisfy the given condition.

Time Complexity: O(log(bound)^2) Generating i and j values takes O(log(bound)^2) time complexity.

Space Complexity: O(log(bound)^2) The space required to store powerful integers in a set is O(log(bound)^2).

Example:

Input: x = 2, y = 3, bound = 10 Output: [2, 3, 4, 5, 7, 9, 10]

Explanation: x=2 and y=3

i=0 j=0 nums=2^0 + 3^0= 2 -> Add number to the set -> {2}

i=0 j=1 nums=2^0 + 3^1= 3 -> Add number to the set -> {2,3}

i=0 j=2 nums=2^0 + 3^2=4 -> Add number to the set -> {2,3,4}

i=1 j=0 nums=2^1 + 3^0=5 -> Add number to the set -> {2,3,4,5}

i=1 j=1 nums=2^1 + 3^1= 7 -> Add number to the set -> {2,3,4,5,7}

i=1 j=2 nums=2^1 + 3^2= 9 -> Add number to the set -> {2,3,4,5,7,9}

i=1 j=3 nums=2^1 + 3^3= 11 -> break as it is greater than 10. i=2 j=0 nums=2^2 + 3^0= 8 -> break as it is greater than 10.

Final set = {2, 3, 4, 5, 7, 9} Convert set to a list. return [2, 3, 4, 5, 7, 9] as the output.

1