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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Powerful Integers and Math problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →