# Powerful Integers (Leetcode 970)

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 xi + yj 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 = 20 + 30
3 = 21 + 30
4 = 20 + 31
5 = 21 + 31
7 = 22 + 31
9 = 23 + 30
10 = 20 + 32
``````

Example 2:

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

### Constraints

• `1 <= x, y <= 100`
• `0 <= bound <= 106`

## Solution

The problem is simply find out the integers (i , j) which satisfy the condition xi + yj <= 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, yi = 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

### Complexity Analysis

The operations it takes x to reach bounds is LogX(Bound). Similarly the max operations for y to reach bounds is LogY(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))