Powerful Integers

Medium
1285.

Powerful Integers

Powerful Integers is a medium coding problem on hash table, math and enumeration, asked in Amazon and Apple interviews.

An integer is powerful for x and y if it can be written as x^i + y^j for some integers i >= 0 and j >= 0.

Return every powerful integer that is less than or equal to bound, each listed once, in increasing order.

Example 1

Input
x = 2, y = 3, bound = 10
Output
[2,3,4,5,7,9,10]
Explanation
2 = 1+1, 3 = 2+1, 4 = 1+3, 5 = 2+3, 7 = 4+3, 9 = 8+1, 10 = 1+9.

Example 2

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

Example 3

Input
x = 2, y = 1, bound = 10
Output
[2,3,5,9]
Explanation
Every power of 1 is 1, so the values are 2^i + 1.

Constraints

  • 1 <= x, y <= 100
  • 0 <= bound <= 10^6
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} x
 * @param {number} y
 * @param {number} bound
 * @return {number[]}
 */
var powerfulIntegers = function(x, y, bound) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Powerful Integers — Solution in Python, Java & C++

Powerful Integers solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on hash table and math.

Powerful Integers is a medium coding problem on hash table, math and enumeration, asked in Amazon and Apple interviews.

  • Difficulty: Medium
  • Topics: Hash Table, Math, Enumeration
  • Asked at: Amazon, Apple
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

An integer is powerful for x and y if it can be written as x^i + y^j for some integers i >= 0 and j >= 0.

Return every powerful integer that is less than or equal to bound, each listed once, in increasing order.

Example 1

Input: x = 2, y = 3, bound = 10
Output: [2,3,4,5,7,9,10]
Explanation: 2 = 1+1, 3 = 2+1, 4 = 1+3, 5 = 2+3, 7 = 4+3, 9 = 8+1, 10 = 1+9.

Example 2

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

Example 3

Input: x = 2, y = 1, bound = 10
Output: [2,3,5,9]
Explanation: Every power of 1 is 1, so the values are 2^i + 1.

Constraints

  • 1 <= x, y <= 100
  • 0 <= bound <= 10^6

Hints for Powerful Integers

  1. Hint 1

    How many powers of x are at most 10^6? For x >= 2, no more than 20.

  2. Hint 2

    So try every pair of a power of x and a power of y that keeps the sum within bound, and collect the sums in a set (different pairs can give the same sum).

  3. Hint 3

    Base 1 is the trap: 1^i is always 1, so a loop that multiplies by x until it exceeds the bound never ends. Stop after the first power when the base is 1.

How to solve Powerful Integers

There are at most about 20 × 20 candidate sums, so enumerate every pair of powers, de-duplicate with a set, and sort.

Approach

  1. For a = 1, x, x^2, … while a <= bound:
  2. For b = 1, y, y^2, … while a + b <= bound, add a + b to a set; if y == 1, stop after the first b.
  3. If x == 1, stop after the first a.
  4. Return the set's values in increasing order.

Why it works

Every powerful integer within the bound is some x^i + y^j with both terms at most bound, and the loops visit every such pair: powers only grow, so once a sum exceeds bound larger exponents cannot help. A base of 1 has a single distinct power, which is why its loop runs once. The set removes sums produced by several pairs, such as 1 + 4 = 4 + 1 when x = y.

Complexity

  • Time — O(log_x(bound) · log_y(bound) · log(answer)) — at most a few hundred sums
  • Space — O(number of results)

Pitfalls

  • An infinite loop when x or y is 1.
  • Duplicates: with x = y = 2, 3 = 1 + 2 = 2 + 1 must appear once.
  • bound can be 0 or 1, where the answer is empty (the smallest powerful integer is 2).

Reference solution

Python

from typing import List

def powerfulIntegers(x: int, y: int, bound: int) -> List[int]:
    found = set()
    a = 1
    while a <= bound:
        b = 1
        while a + b <= bound:
            found.add(a + b)
            if y == 1:
                break
            b *= y
        if x == 1:
            break
        a *= x
    return sorted(found)

Java

public static int[] powerfulIntegers(int x, int y, int bound) {
    TreeSet<Integer> found = new TreeSet<>();
    for (long a = 1; a <= bound; a *= x) {
        for (long b = 1; a + b <= bound; b *= y) {
            found.add((int) (a + b));
            if (y == 1) break;
        }
        if (x == 1) break;
    }
    int[] out = new int[found.size()];
    int i = 0;
    for (int v : found) out[i++] = v;
    return out;
}

C++

vector<int> powerfulIntegers(int x, int y, int bound) {
    set<int> found;
    for (long long a = 1; a <= bound; a *= x) {
        for (long long b = 1; a + b <= bound; b *= y) {
            found.insert((int)(a + b));
            if (y == 1) break;
        }
        if (x == 1) break;
    }
    return vector<int>(found.begin(), found.end());
}

JavaScript

var powerfulIntegers = function(x, y, bound) {
    var found = new Set();
    for (var a = 1; a <= bound; a *= x) {
        for (var b = 1; a + b <= bound; b *= y) {
            found.add(a + b);
            if (y === 1) break;
        }
        if (x === 1) break;
    }
    return Array.from(found).sort(function(p, q) { return p - q; });
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 439 hash table problems · the whole catalogue

Learn the technique: Hashing: Hash Maps and Hash Sets