970. Powerful Integers

MediumHash TableMath

Problem Description

Given three integers x, y, and bound, the task is to find all unique powerful integers. A powerful integer is defined as the sum of x raised to the power of i and y raised to the power of j, where i and j are non-negative integers (i.e., i >= 0 and j >= 0). The twist here is that we are only interested in those sums that do not exceed a given limit, bound. The result should be a list of these powerful integers, and each should only appear once, regardless of the order they're presented in.

Intuition

The key to solving this problem is recognizing that we only need a reasonable range of powers for x and y since they're bound by a maximum value. To solve this efficiently, we think of what happens when we increment these exponents: as i or j increase, the value of x^i or y^j grows exponentially. So, even if x and y are as small as 2, by the time they are raised to the 20th power, they are already greater than 10^6 (2^20 > 10^6), which exceeds the typical constraints of bound.

Based on this observation, we can intelligently limit our search for potential values of i and j. This way we avoid calculating large powers that would exceed the bound. More specifically, we need to ensure the sums x^i + y^j are within the bound, and we only need to look for values of i and j that meet this requirement.

When either x or y is 1, it doesn't make sense to keep increasing the power, because 1 raised to any power is still 1. This means that if x or y is 1, we loop through its power only once, rather than continuing to increase it, which would just give us the same result. If neither x nor y is 1, we proceed with the nested loop, ensuring each time that the sum x^i + y^j does not exceed bound.

The solution uses a set to collect the sums to automatically handle duplicates and ensure that each powerful integer is only counted once. After looping through all potential combinations, we convert the set to a list to provide the answer that matches the problem's expected return type.

Learn more about Math patterns.

Solution Approach

The implementation strategy for finding all powerful integers within the specified bound takes advantage of some basic algorithmic principles and the properties of mathematical exponents. Let's go step by step through what the provided Python solution does:

Set Data Structure: The solution uses a Python set, called ans, as the primary data structure to store the powerful integers. The set is chosen because it can automatically manage duplicates, which means any sum computed more than once will only be stored once in the set.
Loop Bounds for Efficiency: To keep the algorithm efficient, we determine the powers of x and y within a restricted loop bound, as the Reference Solution Approach suggests. If x and y are both greater than 1, i and j will never need to exceed 20 because x^i or y^j would be greater than 10^6. Hence, we can cap our loop to not exceed the bound.
Nested While Loop and Exponentiation: A double-nested while loop is employed to go through all the viable powers of x and y. The outer loop is for the variable a representing x^i, and the inner loop for b representing y^j.
Breaking Conditions: Within each loop iteration, we check that the current powers' sum a + b is less than or equal to bound. If it isn't, we don't need to explore higher powers of y for the current x exponent and break out of the inner loop. Similarly, if x is 1, increasing i won't change the value of a, so we break out of the outer loop. The same logic applies for y.
Early Termination: If we find that x or y is 1, we can optimize further by breaking out of the respective loop immediately after the first iteration. This is because any exponent of 1 is still 1, and so further iterations would not provide any new sums.
Adding to the Set: For each valid pair of powers found within the loops, the sum a + b is added to the set ans.
Final Result: Once all potential a and b values have been tried, the set ans contains all the unique powerful integers that fall within the bound. The set is cast to a list, and then the list is returned as the final result.

The above solution ensures we consider all possible sums within the constraint efficiently without redundant calculations or concerns about duplicates.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let’s assume our input values are x = 2, y = 3, and bound = 10. Our goal is to find all unique powerful integers that can be represented as 2^i + 3^j where i and j are non-negative integers, and the result does not exceed the bound of 10.

Step-by-step Calculation:

Initial Set: We start with an empty set ans to hold the values of all unique powerful integers.
Identify Loop Bounds: We assume the cutoff for i and j is 2 because if x or y is raised to the power of 3, the result is 2^3 = 8 and 3^3 = 27, and any sum involving 27 would exceed our bound of 10.
Nested Loops:
- Start with i = 0; calculate a = 2^i = 2^0 = 1.
- Now enter the inner loop with j = 0; calculate b = 3^j = 3^0 = 1.
- Check if a + b = 1 + 1 = 2 is less than or equal to 10, it is, so add 2 to our set ans.
- Stay in the inner loop with j = 1; calculate b = 3^j = 3^1 = 3.
- Check if a + b = 1 + 3 = 4 is less than or equal to 10, it is, so add 4 to our set ans.
- Increment j to 2; calculate b = 3^j = 3^2 = 9.
- Check if a + b = 1 + 9 = 10 is less than or equal to 10, it is, so add 10 to our set ans.
- j = 3 would exceed our cutoff, so we do not increment j further.
Next Outer Loop Iteration:
- With i = 1; calculate a = 2^i = 2^1 = 2.
- Repeat the inner loop with j = 0 through 2, adding 2 + 1, 2 + 3, and 2 + 9 to our set ans if not exceeding the bound.
Last Outer Loop Iteration:
- With i = 2; calculate a = 2^i = 2^2 = 4.
- Repeat the inner loop with j = 0 and j = 1, adding 4 + 1 and 4 + 3 to our set ans, but the sum with j = 2 would exceed the bound, so it's not added.
Loop Completion: Once all combinations of i and j have been tested, we find that no further valid powerful integers can be formed without exceeding the bound.
Result Construction: The values in our set ans are the powerful integers: {2, 4, 5, 10}.

After converting this set to a list, the final answer we return is [2, 4, 5, 10]. It's important to note that the order of these integers does not matter, and the uniqueness is guaranteed by the set data structure.

Solution Implementation

1class Solution:
2    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:
3        # Initialize an empty set to hold the unique powerful integers
4        powerful_ints = set()
5      
6        # Initialize the base value for x to 1
7        base_x = 1
8      
9        # Loop through increasing powers of x while it's less than or equal to the bound
10        while base_x <= bound:
11            # Initialize the base value for y to 1
12            base_y = 1
13          
14            # Loop through increasing powers of y and add to base_x while the sum is within the bound
15            while base_x + base_y <= bound:
16                # Add the sum of the powers to the set to ensure uniqueness
17                powerful_ints.add(base_x + base_y)
18              
19                # Multiply base_y by y to get the next power of y
20                base_y *= y
21              
22                # If y is 1, it will always be 1, so break to avoid infinite loop
23                if y == 1:
24                    break
25          
26            # If x is 1, it will always be 1, so break to avoid infinite loop
27            if x == 1:
28                break
29          
30            # Multiply base_x by x to get the next power of x
31            base_x *= x
32      
33        # Convert the set to a list to return the powerful integers
34        return list(powerful_ints)
35

1class Solution {
2  
3    // Function to find powerful integers that can be expressed as x^i + y^j
4    // where i and j are integers, x and y are given values, and the result is less than or equal to the bound.
5    public List<Integer> powerfulIntegers(int x, int y, int bound) {
6        // A set to store the unique powerful integers
7        Set<Integer> powerfulInts = new HashSet<>();
8      
9        // Iterate over the powers of x
10        // a will be x^i
11        for (int exponentOfX = 1; exponentOfX <= bound; exponentOfX *= x) {
12          
13            // Iterate over the powers of y
14            // b will be y^j
15            for (int exponentOfY = 1; exponentOfX + exponentOfY <= bound; exponentOfY *= y) {
16                // Add the sum of the powers of x and y to the set
17                powerfulInts.add(exponentOfX + exponentOfY);
18              
19                // If y is 1, then y^j will always be 1, so we can break the loop to prevent infinite loop
20                if (y == 1) {
21                    break;
22                }
23            }
24          
25            // If x is 1, then x^i will always be 1, so we can break the loop to prevent infinite loop
26            if (x == 1) {
27                break;
28            }
29        }
30      
31        // Convert the set of integers to a list and return it
32        return new ArrayList<>(powerfulInts);
33    }
34}
35

1#include <vector>
2#include <unordered_set>
3using namespace std;
4
5class Solution {
6public:
7    // This method finds all powerful integers within a given bound.
8    // An integer is powerful if it can be expressed as x^i + y^j
9    // where x and y are positive integers and i and j are non-negative integers.
10    vector<int> powerfulIntegers(int x, int y, int bound) {
11        unordered_set<int> powerfulInts; // Use a set to store unique powerful integers.
12      
13        // Iterate over all possible values of x^i where i >= 0
14        // and the result is within the given bound.
15        for (int powX = 1; powX <= bound; powX *= x) {
16          
17            // Iterate over all possible values of y^j where j >= 0
18            // and the sum of x^i and y^j is within the given bound.
19            for (int powY = 1; powX + powY <= bound; powY *= y) {
20                powerfulInts.insert(powX + powY); // Insert the sum into the set.
21              
22                // If y is 1, then y^j will always be 1 and we won't get new sums, break out of the loop.
23                if (y == 1) {
24                    break;
25                }
26            }
27          
28            // If x is 1, then x^i will always be 1 and we won't get new sums, break out of the loop.
29            if (x == 1) {
30                break;
31            }
32        }
33      
34        // Convert the set of powerful integers into a vector and return it.
35        vector<int> result(powerfulInts.begin(), powerfulInts.end());
36        return result;
37    }
38};
39

1/**
2 * Returns an array of unique integers that are the sum of powers of
3 * the given `x` and `y` that are less than or equal to the given `bound`.
4 *
5 * @param {number} x - The base for the first term of the sum.
6 * @param {number} y - The base for the second term of the sum.
7 * @param {number} bound - The upper limit for the sum of powers.
8 * @returns {number[]} - A unique set of integers which are the sum of powers.
9 */
10function powerfulIntegers(x: number, y: number, bound: number): number[] {
11    // Initialize a new Set to store unique sums.
12    const uniqueSums = new Set<number>();
13
14    // Iterate over powers of `x`.
15    for (let powerOfX = 1; powerOfX <= bound; powerOfX *= x) {
16        // Iterate over powers of `y`.
17        for (let powerOfY = 1; powerOfX + powerOfY <= bound; powerOfY *= y) {
18            // Add the sum of the current powers of `x` and `y` to the Set.
19            uniqueSums.add(powerOfX + powerOfY);
20
21            // If `y` is 1, we reach a fixed point as `y` to any power is still 1.
22            // No need to proceed further in the inner loop.
23            if (y === 1) {
24                break;
25            }
26        }
27
28        // If `x` is 1, we reach a fixed point as `x` to any power is still 1.
29        // No need to proceed further in the outer loop.
30        if (x === 1) {
31            break;
32        }
33    }
34
35    // Convert the Set of unique sums into an array and return it.
36    return Array.from(uniqueSums);
37}
38
39// Usage example:
40// const result = powerfulIntegers(2, 3, 10);
41// console.log(result); // Output may be something like [2, 3, 4, 5, 7, 9, 10]
42

Time and Space Complexity

The time complexity of the code is determined by the nested while loops that iterate over the variables a and b. Since both a and b are exponentially increased by multiplying by x and y, the number of iterations is proportional to the logarithm of the bound. More specifically, the outer while loop runs until a exceeds bound, which happens after O(log_x(bound)) iterations if x > 1, and only once if x == 1. Similarly, for each value of a, the inner while loop runs until b exceeds bound - a, which happens after O(log_y(bound)) iterations if y > 1, and only once if y == 1. The overall time complexity is, therefore, O(log_x(bound) * log_y(bound)), which can also be expressed as O((log bound)^2) assuming x and y are greater than 1. If either x or y is 1, the complexity would drop to O(log bound) or O(1) for x and y being 1 respectively.

The space complexity is determined by the size of the set ans, which contains all the different sums of a and b that do not exceed bound. In the worst case, every pair (a, b) is unique before reaching the bound. The size of the set would then be proportional to the number of pairs we can form, which is O(log_x(bound) * log_y(bound)), hence making the space complexity O((log bound)^2) for x and y greater than 1.

In summary:

Time Complexity: O((log bound)^2) when x > 1 and y > 1; O(log bound) when either x or y is 1; O(1) when both x and y are 1.
Space Complexity: O((log bound)^2) for x and y greater than 1; otherwise, it will be less depending on the number of unique sums obtainable when either x or y equals 1.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

dp[i] = dp[i - 1] + dp[i - 2]

dp[i] = dp[i - 1] + 1

dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]

dp[i] = dp[i - 1]

I don’t know