970. Powerful Integers Solution & Code

The problem

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 xⁱ + y^j 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 = 2⁰ + 3⁰
3 = 2¹ + 3⁰
4 = 2⁰ + 3¹
5 = 2¹ + 3¹
7 = 2² + 3¹
9 = 2³ + 3⁰
10 = 2⁰ + 3²

Example 2:

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

Constraints:

1 <= x, y <= 100
0 <= bound <= 10⁶

Approach overview

Problem Overview: You are given integers x, y, and bound. A number is considered powerful if it can be written as x^i + y^j where i >= 0 and j >= 0. The task is to generate all unique powerful integers that are less than or equal to bound.

Approach 1: Iterative Power Combination (O(log_x(bound) * log_y(bound)) time, O(k) space)

This approach enumerates all valid powers of x and y whose sum does not exceed bound. Start with x^0 and repeatedly multiply by x until the value exceeds the bound. Do the same for y. For every pair of powers, compute x^i + y^j. If the result is within the bound, store it in a set to avoid duplicates. The key idea is that powers grow exponentially, so the number of iterations is small—roughly log_x(bound) for x and log_y(bound) for y. A hash set guarantees uniqueness and constant-time insertion. This solution relies on simple enumeration and is easy to implement using concepts from math and hash tables.

Approach 2: Optimized Early Termination (O(log_x(bound) * log_y(bound)) time, O(k) space)

This version improves the iteration by handling edge cases where x == 1 or y == 1. If either base is 1, repeated powers do not change the value (e.g., 1^i = 1). Without special handling, the loop would run indefinitely. The optimized solution breaks the loop once the base equals 1 or once the next power exceeds the bound. During enumeration, compute x^i + y^j and insert valid sums into a set. Early termination reduces unnecessary iterations and keeps the implementation safe for edge cases. This technique is a practical optimization when performing enumeration over exponential sequences.

Recommended for interviews: Interviewers typically expect the enumeration strategy with a hash set. Start by explaining that brute-force over all integers up to the bound would be inefficient. Then show that the number of powers of x and y below the bound is logarithmic, making enumeration feasible. Demonstrating the early termination optimization for x == 1 or y == 1 shows attention to edge cases and production-quality thinking.

Approach 1: Approach 1: Iterative Power Combination

This approach involves iterating over possible powers of x and y, and calculating their sums while keeping the sum within the bound. We use two nested loops: one to iterate over powers of x and the other to iterate over powers of y. The results are stored in a set to ensure uniqueness.

Python

def powerful_integers(x, y, bound):
    powerful = set()
    i, j = 0, 0
    while x**i <= bound:
        j = 0
        while x**i + y**j <= bound:
            powerful.add(x**i + y**j)
            if y == 1:
                break
            j += 1
        if x == 1:
            break
        i += 1
    return list(powerful)

C++

#include <iostream>
#include <vector>
#include <unordered_set>
#include <cmath>

std::vector<int> powerfulIntegers(int x, int y, int bound) {
    std::unordered_set<int> powerful;
    for (int i = 0; pow(x, i) <= bound && i < 20; ++i) {
        for (int j = 0; pow(y, j) <= bound; ++j) {
            int sum = pow(x, i) + pow(y, j);
            if (sum <= bound) {
                powerful.insert(sum);
            }
            if (y == 1) break;
        }
        if (x == 1) break;
    }
    return std::vector<int>(powerful.begin(), powerful.end());
}

The function powerful_integers calculates all powerful integers within the given bound. It uses nested loops where the outer loop iterates over powers of x and the inner loop iterates over powers of y. It calculates the sum x^i + y^j and checks if it's within the bound. If so, it adds the sum to a set. This set ensures all elements are unique.

Complexity

Time Complexity: O(log(bound)^2) since the loops iterate logarithmically with respect to the bound.
Space Complexity: O(n) where n is the number of unique powerful integers within the bound.

Try this approach in the editor

Approach 2: Approach 2: Optimized Early Termination

In this approach, we optimize the early termination condition by ensuring that we stop iterating as soon as additional powers do not contribute to any new sums within the bound. This prevents unnecessary iterations and computations.

Java

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class PowerfulIntegers {
    public List<Integer> powerfulIntegers(int x, int y, int bound) {
        Set<Integer> powerful = new HashSet<>();
        int xi = 1;
        while (xi <= bound) {
            int yj = 1;
            while (xi + yj <= bound) {
                powerful.add(xi + yj);
                if (y == 1) break;
                yj *= y;
            }
            if (x == 1) break;
            xi *= x;
        }
        return new ArrayList<>(powerful);
    }
}

JavaScript

function powerfulIntegers(x, y, bound) {
    const powerful = new Set();
    let xi = 1;
    while (xi <= bound) {
        let yj = 1;
        while (xi + yj <= bound) {
            powerful.add(xi + yj);
            if (y === 1) break;
            yj *= y;
        }
        if (x === 1) break;
        xi *= x;
    }
    return Array.from(powerful);
}

This Java implementation takes a similar approach using HashSet for storing results. The main difference is using multiplicative updates with xi *= x and yj *= y, which helps in reducing unnecessary calculations.

Complexity

Time Complexity: O(log(bound)^2) due to the nested loops.
Space Complexity: O(n), where n is the number of powerful integers found.

Try this approach in the editor

Approach 3: Hash Table + Enumeration

According to the description of the problem, a powerful integer can be represented as x^i + y^j, where i geq 0, j geq 0.

The problem requires us to find all powerful integers that do not exceed bound. We notice that the value range of bound does not exceed 10^6, and 2^{20} = 1048576 \gt 10^6. Therefore, if x geq 2, then i is at most 20 to make x^i + y^j leq bound hold. Similarly, if y geq 2, then j is at most 20.

Therefore, we can use double loop to enumerate all possible x^i and y^j, denoted as a and b respectively, and ensure that a + b leq bound, then a + b is a powerful integer. We use a hash table to store all powerful integers that meet the conditions, and finally convert all elements in the hash table into the answer list and return it.

Note that if x=1 or y=1, then the value of a or b is always equal to 1, and the corresponding loop only needs to be executed once to exit.

The time complexity is O(log^2 bound), and the space complexity is O(log^2 bound).

TypeScript

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

func powerfulIntegers(x int, y int, bound int) (ans []int) {
	s := map[int]struct{}{}
	for a := 1; a <= bound; a *= x {
		for b := 1; a+b <= bound; b *= y {
			s[a+b] = struct{}{}
			if y == 1 {
				break
			}
		}
		if x == 1 {
			break
		}
	}
	for x := range s {
		ans = append(ans, x)
	}
	return ans
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Approach 1: Iterative Power Combination	Time Complexity: O(log(bound)^2) since the loops iterate logarithmically with respect to the bound. Space Complexity: O(n) where n is the number of unique powerful integers within the bound.
Approach 2: Optimized Early Termination	Time Complexity: O(log(bound)^2) due to the nested loops. Space Complexity: O(n), where n is the number of powerful integers found.
Hash Table + Enumeration	–

Complexity analysis

Approach	Time	Space	When to Use
Iterative Power Combination	O(log_x(bound) * log_y(bound))	O(k)	General solution. Straightforward enumeration of powers with a hash set for uniqueness.
Optimized Early Termination	O(log_x(bound) * log_y(bound))	O(k)	Preferred in interviews. Handles edge cases like x=1 or y=1 and avoids unnecessary iterations.

Frequently asked questions

Is Powerful Integers easy or hard?

Powerful Integers is generally considered a medium-level problem. The main difficulty comes from recognizing that brute force over the entire range is unnecessary and that powers grow exponentially, allowing a compact enumeration strategy.

What is the best approach for Powerful Integers?

The best approach enumerates powers of x and y up to the bound and stores valid sums in a hash set. Because powers grow exponentially, there are only about log_x(bound) and log_y(bound) possible values. Combining them gives an efficient O(log_x(bound) * log_y(bound)) time solution with O(k) space for the result set.

What data structure is used in Powerful Integers?

A hash set is the primary data structure. It stores generated values of x^i + y^j and automatically removes duplicates when different power combinations produce the same sum. Enumeration with simple loops is used alongside the set.

What is the time complexity of Powerful Integers?

The time complexity is O(log_x(bound) * log_y(bound)). Each loop generates powers of x and y until they exceed the bound, which takes logarithmic steps because the values grow exponentially. Space complexity is O(k), where k is the number of unique powerful integers produced.

Powerful Integers Python or Java solution approach?

Both Python and Java implementations follow the same idea: generate powers of x and y with loops, compute sums, and insert them into a set. Convert the set to a list at the end. Early termination checks for x == 1 or y == 1 prevent unnecessary iterations.

Is Powerful Integers asked at Google, Amazon, or Meta?

Problems involving power enumeration and hash sets appear in interviews at companies like Amazon and Google. While the exact problem may vary, the underlying concepts—mathematical enumeration, hash set deduplication, and careful handling of exponential growth—are common interview patterns.

How to solve Powerful Integers in O(log_x(bound) * log_y(bound))?

Generate powers of x and y starting from 1. For every pair (x^i, y^j), compute the sum and check if it is less than or equal to the bound. Insert valid results into a hash set to avoid duplicates. Stop generating powers when the next multiplication exceeds the bound, and break early when x or y equals 1.

Powerful Integers solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Iterative Power Combination

Approach 2: Approach 2: Optimized Early Termination

Approach 3: Hash Table + Enumeration

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Powerful Integers solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Iterative Power Combination

Approach 2: Approach 2: Optimized Early Termination

Approach 3: Hash Table + Enumeration

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems