Difficulty: Medium Link: Day 30: April Leetcoding Challenge

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. You may return the answer in **any order**. In your answer, each value should occur **at most once**.

**Example 1:**

**Input:** x = 2, y = 3, bound = 10
**Output:** [2,3,4,5,7,9,10]
**Explanation:**
2 = 2^{0} + 3^{0}
3 = 2^{1} + 3^{0}
4 = 2^{0} + 3^{1}
5 = 2^{1} + 3^{1}
7 = 2^{2} + 3^{1}
9 = 2^{3} + 3^{0}
10 = 2^{0} + 3^{2}

**Example 2:**

**Input:** x = 3, y = 5, bound = 15
**Output:** [2,4,6,8,10,14]

**Constraints**

`1 <= x, y <= 100`

`0 <= bound <= 10`

^{6}

**Solution**

The problem is simply find out the integers **(i , j)** which satisfy the condition **x ^{i} + y^{j} <= bound**. We can use brute force to iterate with two nested loops and check if sum of both terms is less than bounds. We can use a

**set**structure to prevent duplicate answers. Then we can have our nested loops increment the power of the

**x**and

**y**values while adding the appropriate results to our set. The maximum value of any terms compounded with x or y is bound – 1 (Why because

**x, y >= 1,**so if any of them becomes 1 then the maximum value of other term = bound – 1).

### Edge Case

We need to take care of the case when **x or y = 1**. Let us say y = 1, then for every power i, y^{i} = 1 and it will become an *infinite loop*. So in the end of the consecutive loops , *we can check for x = 1 and y = 1 and break out because all the possible values of other terms would have been achieved in the current iteration.*

## Code

**Swift**

### Java

### Python

### Complexity Analysis

The operations it takes x to reach bounds is Log_{X}(Bound). Similarly the max operations for y to reach bounds is Log_{Y}(Bound). Therefore total operations would be in order of O(LogX(Bound) * LogY(Bound)) which is huge because with increasing powers, there would be limited integers satisfying the conditions. Same would be for space.

**Time = O(LogX(Bound) * LogY(Bound))**

**Space = O(LogX(Bound) * LogY(Bound))**