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) {
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
50 const val = x ** i + y ** j
51
52 if (val <= bound) {
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