Given three integers x, y, and bound, return a list of all the powerful integers that have a value less than or equal tobound.
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.
Constraints
1 <= x, y <= 100
0 <= bound <= 106
Approach
Links
GeeksforGeeks
ProgramCreek
YouTube
Examples
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
Input: x = 3, y = 5, bound = 15
Output: [2, 4, 6, 8, 10, 14]
Solutions
/**
* Time complexity :
* Space complexity :
*/
class Solution {
public List<Integer> powerfulIntegers(int x, int y, int bound) {
int a = x == 1 ? bound : (int) (Math.log(bound) / Math.log(x));
int b = y == 1 ? bound : (int) (Math.log(bound) / Math.log(y));
HashSet<Integer> powerfulIntegers = new HashSet<Integer>();
for (int i = 0; i <= a; i++) {
for (int j = 0; j <= b; j++) {
int value = (int) Math.pow(x, i) + (int) Math.pow(y, j);
if (value <= bound) {
powerfulIntegers.add(value);
}
// No point in considering other powers of "1".
if (y == 1) {
break;
}
}
if (x == 1) {
break;
}
}
return new ArrayList<Integer>(powerfulIntegers);
}
}
/**
* Time complexity :
* Space complexity :
*/
class Solution {
public List<Integer> powerfulIntegers(int x, int y, int bound) {
List<Integer> result = null;
Set<Integer> powerfulInts = new HashSet();
if(bound > 1) {
for(int p1 = 1; p1 < bound; p1 *= x) {
for(int p2 = 1; p1 + p2 <= bound; p2 *= y) {
powerfulInts.add(p1 + p2);
if(y == 1) {
break;
}
}
if(x == 1) {
break;
}
}
}
return new ArrayList(powerfulInts);
}
}