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

Swift

class Solution {
func powerfulIntegers(_ x: Int, _ y: Int, _ bound: Int) -> [Int] {
guard bound >= 2 else{
return []
}
var set = Set<Int>()
var powerX = 1
for i in 1..<bound where powerX <= bound{
var powerY = 1
while powerX + powerY <= bound {
set.insert(powerX + powerY)
powerY *= y
if y == 1 {
break
}
}
if x == 1 {
break
}
powerX *= x
}
return Array(set)
}
}

Java

public List<Integer> powerfulIntegers(int x, int y, int bound) {
Set<Integer> set = new HashSet();
for(int i=1; i<=bound; i*=x) {
for(int j=1; i+j <= bound; j*=y) {
set.add(i+j);
if(y == 1) break;
}
if(x == 1) break;
}
return new ArrayList(set);
}

Python

class Solution:
def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:
ans, xi = set(), 1
while xi < bound:
yj = 1
while xi + yj <= bound:
ans.add(xi + yj)
if y == 1: break
yj *= y
if x == 1: break
xi *= x
return list(ans)

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))

Leave a Reply

Your email address will not be published. Required fields are marked *