1
var getKth = function (lo, hi, k) {
2
  const dp = new Map();
3
  dp.set(1, 0);
4
  const powerVals = [];
5
  for (let num = lo; num <= hi; ++num) {
6
    powerVals.push([num, findPowerVal(num, dp)]);
7
  }
8
  const heap = new MinHeap();
9
  heap.build(powerVals);
10
  let top;
11
  while (k--) {
12
    // O(klogn)
13
    top = heap.removeTop();
14
  }
15
  return top[0];
16
};
17

18
function findPowerVal(num, dp) {
19
  if (dp.has(num)) {
20
    return dp.get(num);
21
  }
22
  let powerVal;
23
  if (num % 2 === 0) {
24
    powerVal = findPowerVal(num / 2, dp) + 1;
25
  } else {
26
    powerVal = findPowerVal(3 * num + 1, dp) + 1;
27
  }
28
  dp.set(num, powerVal);
29
  return dp.get(num);
30
}
31

32
class Heap {
33
  constructor(property) {
34
    this.data = [];
35
  }
36
  size() {
37
    return this.data.length;
38
  }
39
  build(arr) {
40
    // O(n)
41
    this.data = [...arr];
42
    for (let i = Math.floor((this.size() - 1) / 2); i >= 0; --i) {
43
      this.heapify(i);
44
    }
45
  }
46
  heapify(i) {
47
    // O(logn)
48
    const left = 2 * i + 1,
49
      right = 2 * i + 2;
50
    let p = i;
51
    if (left < this.size() && this.compare(left, p)) {
52
      p = left;
53
    }
54
    if (right < this.size() && this.compare(right, p)) {
55
      p = right;
56
    }
57
    if (p !== i) {
58
      [this.data[p], this.data[i]] = [this.data[i], this.data[p]];
59
      this.heapify(p);
60
    }
61
  }
62
  removeTop() {
63
    // O(logn)
64
    if (this.size() === 1) {
65
      return this.data.pop();
66
    }
67
    const top = this.data[0];
68
    [this.data[0], this.data[this.size() - 1]] = [
69
      this.data[this.size() - 1],
70
      this.data[0],
71
    ];
72
    this.data.pop();
73
    this.heapify(0);
74
    return top;
75
  }
76
}
77

78
class MinHeap extends Heap {
79
  constructor() {
80
    super();
81
  }
82
  compare(a, b) {
83
    return (
84
      this.data[a][1] < this.data[b][1] ||
85
      (this.data[a][1] === this.data[b][1] && this.data[a][0] < this.data[b][0])
86
    );
87
  }
88
}