970.强整数

强整数

给定 x、y 和 bound，返回值小于等于 bound 的所有强整数。强整数 = x^i + y^j (i >= 0, j >= 0)。

示例 1:

输入：x = 2, y = 3, bound = 10
输出：[2,3,4,5,7,9,10]

示例 2:

输入：x = 3, y = 5, bound = 15
输出：[2,4,6,8,10,14]

提示:

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

解析

枚举所有可能的 x^i 和 y^j，累加后检查是否在 bound 范围内。

var powerfulIntegers = function (x, y, bound) {
  const result = new Set();

  for (let i = 0; i <= 30; i++) {
    let xi = 1;
    for (let j = 0; j <= 30; j++) {
      const sum = xi + Math.pow(y, j);
      if (sum > bound) break;
      result.add(sum);
      if (y === 1) break;
    }
    if (x === 1) break;
    xi *= x;
  }

  return [...result];
};

时间复杂度 O(log_x(bound) * log_y(bound))，空间复杂度 O(N)。