1
class Solution {
2
  public int getKth(int lo, int hi, int k) {
3

4
    int p = 0;
5
    int[][] powerArr = new int[hi - lo + 1][2];
6

7
    Map<Integer, Integer> memo = new HashMap<>();
8
    for (int i = lo; i <= hi; i++) powerArr[p++] = new int[] {i, getPower(i, memo)};
9

10
    Arrays.sort(powerArr, (a1, a2) -> a1[1] - a2[1] == 0 ? a1[0] - a2[0] : a1[1] - a2[1]);
11

12
    return powerArr[k - 1][0];
13
  }
14

15
  private int getPower(int i, Map<Integer, Integer> memo) {
16
    if (memo.containsKey(i)) return memo.get(i);
17

18
    if (i == 1) return 0;
19

20
    int power = 1 + (i % 2 == 0 ? getPower(i / 2, memo) : getPower(i * 3 + 1, memo));
21

22
    memo.put(i, power);
23
    return power;
24
  }
25
}