Powerful Integers

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

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 <= 10^6

Solution

Method 1 - Enumerate Powers (Bounded Exponents)

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 into a set res.

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 res.
3. If x or y is 1, only use i = 0 or j = 0 respectively to avoid infinite loops.
4. Return the set res as a list.

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.

Code

C++

#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

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

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

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

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

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

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