Powerful Integers - Video Solutions

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.