# LeetCode: Powerful Integers Solution

```.css-ds3kc{display:table-row;}.css-1t8atru{display:table-cell;opacity:0.5;padding-right:var(--chakra-space-6);-webkit-user-select:none;-moz-user-select:none;-ms-user-select:none;user-select:none;text-align:right;}1.css-2qghsv{display:table-cell;}/**2 * @param {number} x3 * @param {number} y4 * @param {number} bound5 * @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 ** j17      if (val <= bound) {18        res.add(val)19      }20      // 1^anything will always be 121      if (y === 1) {22        break23      }24    }25    // 1^anything will always be 126    if (x === 1) {27      break28    }29  }30
31  return Array.from(res)32}33
34// dfs35var 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      continue47    }48
49    visited.add(getKey(i, j))50    const val = x ** i + y ** j51
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}```

leetcode

hash table

math

## Next Post

LeetCode: Prefix And Suffix Search

May 1, 2021

Search Posts