Skip to content

970. Powerful Integers 👍

  • Time:
  • Space: 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
 public:
  vector<int> powerfulIntegers(int x, int y, int bound) {
    unordered_set<int> ans;

    for (int i = 1; i < bound; i *= x) {
      for (int j = 1; i + j <= bound; j *= y) {
        ans.insert(i + j);
        if (y == 1)
          break;
      }
      if (x == 1)
        break;
    }

    return {ans.begin(), ans.end()};
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
  public List<Integer> powerfulIntegers(int x, int y, int bound) {
    Set<Integer> ans = new HashSet<>();

    for (int i = 1; i < bound; i *= x) {
      for (int j = 1; i + j <= bound; j *= y) {
        ans.add(i + j);
        if (y == 1)
          break;
      }
      if (x == 1)
        break;
    }

    return new ArrayList<>(ans);
  }
}

1
2
3
4
5
class Solution:
  def powerfulIntegers(self, x: int, y: int, bound: int) -> list[int]:
    xs = {x**i for i in range(20) if x**i < bound}
    ys = {y**i for i in range(20) if y**i < bound}
    return list({i + j for i in xs for j in ys if i + j <= bound})