Powerful integers

Hash Table Math Enumeration

44.5% acceptance

Feb 25, 2026

421

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 xi + yj 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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn powerful_integers(x: i32, y: i32, bound: i32) -> Vec<i32> {
    let mut set = std::collections::HashSet::new();
    let mut xi = 1i32;
    loop {
      let mut yj = 1i32;
      loop {
        let val = xi + yj;
        if val > bound { break; }
        set.insert(val);
        if y == 1 { break; }
        yj *= y;
      }
      if x == 1 { break; }
      xi *= x;
      if xi > bound { break; }
    }
    set.into_iter().collect()
  }
}