Skip to content

1387. Sort Integers by The Power Value 👍

  • Time: $O(n\log n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
 public:
  int getKth(int lo, int hi, int k) {
    vector<pair<int, int>> powAndVals;  // (pow, val)

    for (int i = lo; i <= hi; ++i)
      powAndVals.emplace_back(getPow(i), i);

    nth_element(powAndVals.begin(), powAndVals.begin() + k - 1,
                powAndVals.end());
    return powAndVals[k - 1].second;
  }

 private:
  int getPow(int n) {
    if (n == 1)
      return 0;
    return 1 + (n % 2 == 0 ? getPow(n / 2) : getPow(n * 3 + 1));
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
  public int getKth(int lo, int hi, int k) {
    int[][] powAndVals = new int[hi - lo + 1][2]; // (pow, val)

    for (int i = lo; i <= hi; ++i)
      powAndVals[i - lo] = new int[] {getPow(i), i};

    Arrays.sort(powAndVals, (a, b) -> a[0] - b[0]);
    return powAndVals[k - 1][1];
  }

  private int getPow(int n) {
    if (n == 1)
      return 0;
    return 1 + (n % 2 == 0 ? getPow(n / 2) : getPow(n * 3 + 1));
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
  def getKth(self, lo: int, hi: int, k: int) -> int:
    return sorted([(self._getPow(i), i) for i in range(lo, hi + 1)])[k - 1][1]

  def _getPow(self, n: int) -> int:
    if n == 1:
      return 0
    if n % 2 == 0:
      return 1 + self._getPow(n // 2)
    return 1 + self._getPow(n * 3 + 1)