Problem

Given three integers x, y, and bound, return a list of all thepowerful 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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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

1
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

Intuition

We want all numbers of the form x^i + y^j <= bound for i, j >= 0. Since x and y can be 1, we must avoid infinite loops. We can enumerate all possible powers of x and y up to bound, and collect all unique sums.

Approach

  1. For all i such that x^i <= bound, and for all j such that y^j <= bound, compute s = x^i + y^j.
  2. If s <= bound, add to a set.
  3. If x or y is 1, only use i=0 or j=0 respectively to avoid infinite loops.
  4. Return the set as a list.

Code

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

#include <vector>
#include <unordered_set>
using namespace std;
vector<int> powerfulIntegers(int x, int y, int bound) {
    unordered_set<int> res;
    for (int a = 1; a < bound + 1; a *= x) {
        for (int b = 1; a + b <= bound; b *= y) {
            res.insert(a + b);
            if (y == 1) break;
        }
        if (x == 1) break;
    }
    return vector<int>(res.begin(), res.end());
}
Go
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

func powerfulIntegers(x int, y int, bound int) []int {
    res := map[int]bool{}
    for a := 1; a < bound+1; a *= x {
        for b := 1; a+b <= bound; b *= y {
            res[a+b] = true
            if y == 1 {
                break
            }
        }
        if x == 1 {
            break
        }
    }
    ans := []int{}
    for k := range res {
        ans = append(ans, k)
    }
    return ans
}
Java
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

import java.util.*;
class Solution {
    public List<Integer> powerfulIntegers(int x, int y, int bound) {
        Set<Integer> res = new HashSet<>();
        for (int a = 1; a < bound + 1; a *= x) {
            for (int b = 1; a + b <= bound; b *= y) {
                res.add(a + b);
                if (y == 1) break;
            }
            if (x == 1) break;
        }
        return new ArrayList<>(res);
    }
}
Kotlin
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

fun powerfulIntegers(x: Int, y: Int, bound: Int): List<Int> {
    val res = mutableSetOf<Int>()
    var a = 1
    while (a < bound + 1) {
        var b = 1
        while (a + b <= bound) {
            res.add(a + b)
            if (y == 1) break
            b *= y
        }
        if (x == 1) break
        a *= x
    }
    return res.toList()
}
Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

def powerfulIntegers(x: int, y: int, bound: int) -> list[int]:
    res = set()
    a = 1
    while a < bound + 1:
        b = 1
        while a + b <= bound:
            res.add(a + b)
            if y == 1:
                break
            b *= y
        if x == 1:
            break
        a *= x
    return list(res)
Rust
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

use std::collections::HashSet;
fn powerful_integers(x: i32, y: i32, bound: i32) -> Vec<i32> {
    let mut res = HashSet::new();
    let mut a = 1;
    while a < bound + 1 {
        let mut b = 1;
        while a + b <= bound {
            res.insert(a + b);
            if y == 1 { break; }
            b *= y;
        }
        if x == 1 { break; }
        a *= x;
    }
    res.into_iter().collect()
}
TypeScript
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

export function powerfulIntegers(x: number, y: number, bound: number): number[] {
    const res = new Set<number>();
    for (let a = 1; a < bound + 1; a *= x) {
        for (let b = 1; a + b <= bound; b *= y) {
            res.add(a + b);
            if (y === 1) break;
        }
        if (x === 1) break;
    }
    return Array.from(res);
}

Complexity

  • ⏰ Time complexity: O(log(bound) * log(bound)) (since i and j are at most log_x(bound) and log_y(bound)).
  • 🧺 Space complexity: O(N) where N is the number of unique results.