1387. Sort Integers by The Power Value LeetCode Solution

In this guide, you will get 1387. Sort Integers by The Power Value LeetCode Solution with the best time and space complexity. The solution to Sort Integers by The Power Value problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Sort Integers by The Power Value solution in C++
Sort Integers by The Power Value solution in Java
Sort Integers by The Power Value solution in Python
Additional Resources

1387. Sort Integers by The Power Value LeetCode Solution image

Problem Statement of Sort Integers by The Power Value

The power of an integer x is defined as the number of steps needed to transform x into 1 using the following steps:

if x is even then x = x / 2
if x is odd then x = 3 * x + 1

For example, the power of x = 3 is 7 because 3 needs 7 steps to become 1 (3 –> 10 –> 5 –> 16 –> 8 –> 4 –> 2 –> 1).
Given three integers lo, hi and k. The task is to sort all integers in the interval [lo, hi] by the power value in ascending order, if two or more integers have the same power value sort them by ascending order.
Return the kth integer in the range [lo, hi] sorted by the power value.
Notice that for any integer x (lo <= x <= hi) it is guaranteed that x will transform into 1 using these steps and that the power of x is will fit in a 32-bit signed integer.

Example 1:

Input: lo = 12, hi = 15, k = 2
Output: 13
Explanation: The power of 12 is 9 (12 –> 6 –> 3 –> 10 –> 5 –> 16 –> 8 –> 4 –> 2 –> 1)
The power of 13 is 9
The power of 14 is 17
The power of 15 is 17
The interval sorted by the power value [12,13,14,15]. For k = 2 answer is the second element which is 13.
Notice that 12 and 13 have the same power value and we sorted them in ascending order. Same for 14 and 15.

Example 2:

Input: lo = 7, hi = 11, k = 4
Output: 7
Explanation: The power array corresponding to the interval [7, 8, 9, 10, 11] is [16, 3, 19, 6, 14].
The interval sorted by power is [8, 10, 11, 7, 9].
The fourth number in the sorted array is 7.

Constraints:

1 <= lo <= hi <= 1000
1 <= k <= hi – lo + 1

Complexity Analysis

Time Complexity: O(n\log n)
Space Complexity: O(n)

1387. Sort Integers by The Power Value LeetCode Solution in C++

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));
  }
};
/* code provided by PROGIEZ */

1387. Sort Integers by The Power Value LeetCode Solution in Java

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) -> Integer.compare(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));
  }
}
// code provided by PROGIEZ

1387. Sort Integers by The Power Value LeetCode Solution in Python

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)
 # code by PROGIEZ