Skip to main content

970. Powerful Integers

medium

Given x, y, and bound, list every value <= bound that equals x^i + y^j for non-negative i, j. Two nested logarithmic loops + dedup — classic small-search-space enumeration.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

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^i + 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.

Constraints

  • 1 <= x, y <= 100
  • 0 <= bound <= 10^6

Examples

Example 1

Input
x = 2, y = 3, bound = 10
Output
[2,3,4,5,7,9,10]

Explanation: 2 = 2^0 + 3^0; 3 = 2^1 + 3^0; 4 = 2^0 + 3^1; 5 = 2^1 + 3^1; 7 = 2^2 + 3^1; 9 = 2^3 + 3^0; 10 = 2^0 + 3^2.

Example 2

Input
x = 3, y = 5, bound = 15
Output
[2,4,6,8,10,14]

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

The number of distinct i with x^i <= bound is at most log_x(bound). Same for j. Both small even for large bound.

Hint 2

Nested loop: for x_power starting at 1 while x_power <= bound, and inside for y_power starting at 1 while x_power + y_power <= bound — add x_power + y_power to a set.

Hint 3

Edge case: when x or y is 1, x_power stays at 1 forever — break out of the inner loop after one iteration.

Hint 4

Return the set as a list.

Solution approach

Reveal approach

Brute-force enumerate. Outer loop: x_power = 1; while x_power <= bound: inner loop: y_power = 1; while x_power + y_power <= bound: add x_power + y_power to a hash set. Multiply y_power by y; if y == 1, break out of the inner loop to avoid infinite loop. After the inner loop, multiply x_power by x; if x == 1, break out of the outer loop. Return list(set). Why this terminates: with x >= 2, log_x(bound) <= 20 iterations even for bound = 10^6. With x == 1, the early break handles the constant power 1. O(log^2(bound)) time and answer size, O(answer) space.

Complexity

Time
O((log n)^2)
Space
O((log n)^2)

Related patterns

  • math
  • hash-set

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon

More Math practice problems

See all Math problems →