Skip to main content
Talentd

Powerful Integers - Solution & Explanation

MediumHash TableMathEnumeration13 min read
Practice this problem

Problem Statement

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 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.

 

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 <= 106

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.

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.

Code

PythonC++

Python

C++

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.

This JavaScript function employs a similar logic to previous approaches but uses multiplicative updates instead of powers for progression through x^i and y^j. It utilizes Set for uniqueness and converts the result to an array for the final output.

Code

JavaScriptJava

JavaScript

Java

Complexity

Time Complexity: O(log(bound)^2) as it bounds progression over the log of the bound value.
Space Complexity: O(n) where n is the number of unique powerful integers.

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).

Code

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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) as it bounds progression over the log of the bound value.
Space Complexity: O(n) where n is the number of unique powerful integers.

Hash Table + Enumeration—

Detailed Complexity Analysis

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

Video Solution

Powerful Integers | Live Coding with Explanation | Leetcode - 970 • Algorithms Made Easy • 2,354 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Powerful Integers with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count the Number of Powerful Integers