# 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> 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)