LeetCode: Powerful Integers Solution

1/**
2 * @param {number} x
3 * @param {number} y
4 * @param {number} bound
5 * @return {number[]}
6 */
7var powerfulIntegers = function (x, y, bound) {
8  const res = new Set()
9  const [X, Y] = [
10    x === 1 ? bound : Math.floor(Math.log(bound) / Math.log(x)),
11    y === 1 ? bound : Math.floor(Math.log(bound) / Math.log(y)),
12  ]
13
14  for (let i = 0; i <= X; i++) {
15    for (let j = 0; j <= Y; j++) {
16      const val = x ** i + y ** j
17      if (val <= bound) {
18        res.add(val)
19      }
20      // 1^anything will always be 1
21      if (y === 1) {
22        break
23      }
24    }
25    // 1^anything will always be 1
26    if (x === 1) {
27      break
28    }
29  }
30
31  return Array.from(res)
32}
33
34// dfs
35var powerfulIntegers = function (x, y, bound) {
36  const res = new Set()
37  const visited = new Set()
38  const stack = [[0, 0]]
39
40  const getKey = (i, j) => `${i}-${j}`
41
42  while (stack.length > 0) {
43    const [i, j] = stack.pop()
44
45    if (visited.has(getKey(i, j))) {
46      continue
47    }
48
49    visited.add(getKey(i, j))
50    const val = x ** i + y ** j
51
52    if (val <= bound) {
53      res.add(val)
54      x > 1 && stack.push([i + 1, j])
55      y > 1 && stack.push([i, j + 1])
56    }
57  }
58
59  return Array.from(res)
60}