Powerful Integers

MEDIUM

Description

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⁶

Approaches

Checkout 2 different approaches to solve Powerful Integers. Click on different approaches to view the approach and algorithm in detail.

Brute Force with Pre-calculated Powers

This approach involves pre-calculating all possible powers of x and y that are individually less than the bound. It then iterates through every combination of these powers, checks if their sum is within the bound, and adds the valid sums to a result set. This method is straightforward but less efficient as it doesn't stop checking combinations early even when it's clear the sum will be too large.

Algorithm

Initialize a HashSet<Integer> to store the unique powerful integers.
Generate a list of all powers of x that are less than bound. Let's call this xPowers.
Generate a list of all powers of y that are less than bound. Let's call this yPowers.
Use nested loops to iterate through every power powX in xPowers and every power powY in yPowers.
For each pair, calculate the sum = powX + powY.
If sum <= bound, add the sum to the HashSet.
After iterating through all pairs, convert the HashSet to an ArrayList and return it.

The core idea is to separate the generation of powers from the calculation of their sums. First, we create two lists: one for powers of x (i.e., x^0, x^1, x^2, ...) and one for powers of y (y^0, y^1, y^2, ...), stopping when the power exceeds bound. Then, we use two nested loops to iterate through every pair of powers, one from each list. For each pair (powX, powY), we compute their sum. If the sum is not greater than bound, we add it to a HashSet to ensure all stored values are unique. This approach is exhaustive but fails to use information from the outer loop to optimize the inner loop's work. For example, if x^i is already bound - 1, the inner loop will still check y^j for all j, even though only y^0=1 could potentially produce a valid sum.

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

class Solution {
    public List<Integer> powerfulIntegers(int x, int y, int bound) {
        Set<Integer> result = new HashSet<>();
        List<Integer> xPowers = new ArrayList<>();
        for (int i = 1; i < bound; i *= x) {
            xPowers.add(i);
            if (x == 1) break; // Prevent infinite loop if x is 1
        }

        List<Integer> yPowers = new ArrayList<>();
        for (int i = 1; i < bound; i *= y) {
            yPowers.add(i);
            if (y == 1) break; // Prevent infinite loop if y is 1
        }

        for (int powX : xPowers) {
            for (int powY : yPowers) {
                int sum = powX + powY;
                if (sum <= bound) {
                    result.add(sum);
                } else {
                    // This break makes it slightly more optimal, but the fundamental
                    // approach of checking all pairs is less efficient than the next approach.
                    if (y > 1) break;
                }
            }
        }
        return new ArrayList<>(result);
    }
}

Complexity Analysis

Time Complexity: O(log_x(bound) * log_y(bound)). While the Big-O notation is the same as the optimized approach, the actual number of operations is higher due to the lack of efficient pruning.Space Complexity: O(log_x(bound) + log_y(bound) + N), where N is the number of powerful integers. This is for storing the two lists of powers and the final result set.

Pros and Cons

Pros:

The logic is simple and easy to understand, separating the concerns of generating powers and summing them.

Cons:

Performs many unnecessary computations. For a large powX that is close to bound, the inner loop still iterates through all powY, even though the sum will quickly exceed bound.

Code Solutions

Checking out 4 solutions in different languages for Powerful Integers. Click on different languages to view the code.

class Solution {
public
  List<Integer> powerfulIntegers(int x, int y, int bound) {
    Set<Integer> ans = new HashSet<>();
    for (int a = 1; a <= bound; a *= x) {
      for (int b = 1; a + b <= bound; b *= y) {
        ans.add(a + b);
        if (y == 1) {
          break;
        }
      }
      if (x == 1) {
        break;
      }
    }
    return new ArrayList<>(ans);
  }
}

Video Solution

Watch the video walkthrough for Powerful Integers

Patterns:

MathEnumeration

Data Structures:

Hash Table