Powerful Integers

Problem Statement

The problem involves finding all "powerful integers" that can be derived using two integers, (x) and (y), such that the sum of (x) raised to the power (i) and (y) raised to the power (j) ((x^i + y^j)) does not exceed a given integer (bound). Both (i) and (j) are non-negative integers (i.e., (i, j \geq 0)). The goal is to return a list of these integers where each value is unique and the list can be in any order.

To contextualize, a "powerful integer" is an integer that can be formed as the sum of two terms, where each term is a power of (x) or (y). Given (x), (y), and the upper constraint (bound), the challenge is to find all such integers that fit the criteria specified above.

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

Approach and Intuition

The task requires generating all possible sums (x^i + y^j) that are less than or equal to (bound). Here’s how to tackle it:

1. To generate powerful integers, we need to consider raising (x) and (y) to various powers starting from zero. However, due to rapid growth in value (especially when (x) or (y) are larger), these values can quickly exceed (bound). To optimize this, we'll need to establish upper limits for (i) and (j).

2. Determine the maximum values for (i) and (j) based on (bound):

   • If (x = 1), increasing (i) does not increase the value of (x^i) (it always equals 1); hence, looping over (i) continually won't make a difference unless (y > 1).
   • Use logarithmic calculations to find when (x^i) or (y^j) will exceed (bound) to set practical limits for (i) and (j). The maximum value of (i) (and similarly for (j)) can be approximated by using: ( \text{log}(bound) / \text{log}(x) ), given (x) is not 1.

3. Use nested loops to iterate over possible values of (i) and (j) up to their respective maximums:

   • For each combination of (i) and (j), compute (x^i + y^j).
   • If the result does not exceed (bound), store it in a set (to ensure uniqueness).

4. Once all combinations have been checked, convert the set of powerful integers into a list to be returned as the result.

Example Interpretation

• Example 1: Given (x = 2), (y = 3), and (bound = 10), the function should consider indices where powers like (2^0, 2^1), and (3^0, 3^1) up to their respective limits such that the sum remains within the bound of 10. This is efficiently executed through the steps outlined, focusing particularly on constraints to prevent unnecessary calculations.

• Example 2: With (x = 3), (y = 5), and (bound = 15), we explore combinations similarly, ensuring that only combinations that sum up to 15 or less are considered, using the methodology to efficiently halt exploration when the sum exceeds (bound).

This procedure effectively leverages computational resources by focusing only on feasible calculations, ensures uniqueness with the set data structure, and respects given constraints for producing the final list of powerful integers.

Solutions

class Solution {
    public List<Integer> calculatePowerfulIntegers(int base1, int base2, int limit) {
        int maxExponent1 = base1 == 1 ? limit : (int) (Math.log(limit) / Math.log(base1));
        int maxExponent2 = base2 == 1 ? limit : (int) (Math.log(limit) / Math.log(base2));
            
        HashSet<Integer> result = new HashSet<Integer>();
            
        for (int i = 0; i <= maxExponent1; i++) {
            for (int j = 0; j <= maxExponent2; j++) {
                    
                int sum = (int) Math.pow(base1, i) + (int) Math.pow(base2, j);
                    
                if (sum <= limit) {
                    result.add(sum);
                }
                    
                if (base2 == 1) {
                    break;
                }
            }
                
            if (base1 == 1) {
                break;
            }
        }
            
        return new ArrayList<Integer>(result);
    }
}

class Solution:
    def generatePowerfulIntegers(self, x: int, y: int, upperBound: int) -> List[int]:
        max_i = upperBound if x == 1 else int(log(upperBound, x))
        max_j = upperBound if y == 1 else int(log(upperBound, y))
            
        result_set = set()
            
        for i in range(max_i + 1):
            for j in range(max_j + 1):
                current_sum = x**i + y**j
                    
                if current_sum <= upperBound:
                    result_set.add(current_sum)
                        
                if y == 1:
                    break
                
            if x == 1:
                break
                    
        return list(result_set)