# Sort Integers by The Power Value
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/sort-integers-by-the-power-value)
Canonical: https://scaleengineer.com/dsa/problems/sort-integers-by-the-power-value
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Memoization](https://scaleengineer.com/dsa/patterns/memoization)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
---
## Problem
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`

# Approaches
## Brute Force with Full Sort
This approach directly translates the problem statement into code. We first generate all integers in the given range `[lo, hi]`. For each integer, we calculate its power value by repeatedly applying the given transformation rules until the number becomes 1. We store these numbers and their corresponding power values as pairs. Finally, we sort these pairs based on the power value in ascending order. If two numbers have the same power value, we use the numbers themselves as a tie-breaker, also in ascending order. After sorting, the k-th element in the sorted list is our answer.
**Time:** O(N log N + N * C), where `N = hi - lo + 1` and `C` is the time to calculate the power of a number. The `getPower` function is called for each of the `N` numbers (`N * C`), and then we sort these `N` numbers (`N log N`). · **Space:** O(N), where `N = hi - lo + 1`. This space is required to store the list of `N` pairs, each containing a number and its power value.
**Pros:** Simple to understand and implement.; Directly follows the problem description.
**Cons:** Inefficient due to re-computation of power values for intermediate numbers in the Collatz sequence. For example, calculating the power of 12 (`12 -> 6 -> 3 ...`) involves the same steps as the later part of calculating the power of 6 (`6 -> 3 ...`).
### Explanation
The core of this method is to first compute all the necessary data and then sort it. We define a function to calculate the power value for any given integer. Then, we iterate through the range `[lo, hi]`, compute the power for each integer, and store these `(integer, power)` pairs in a list. Once the list is populated, we perform a standard sort using a custom comparison logic that adheres to the problem's sorting rules. The final step is to pick the element at the `k-1` index from the sorted list.

```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public int getKth(int lo, int hi, int k) {
        List<int[]> pairs = new ArrayList<>();
        for (int i = lo; i <= hi; i++) {
            pairs.add(new int[]{i, getPower(i)});
        }

        // Sort the list using a custom comparator
        Collections.sort(pairs, (a, b) -> {
            if (a[1] != b[1]) {
                return Integer.compare(a[1], b[1]);
            } else {
                return Integer.compare(a[0], b[0]);
            }
        });

        // Return the k-th number
        return pairs.get(k - 1)[0];
    }

    private int getPower(int n) {
        int steps = 0;
        while (n != 1) {
            if (n % 2 == 0) {
                n /= 2;
            } else {
                n = 3 * n + 1;
            }
            steps++;
        }
        return steps;
    }
}
```
### Algorithm
- Create a helper function `getPower(n)` that calculates the power of an integer `n` by simulating the process described (if `n` is even, `n = n / 2`; if `n` is odd, `n = 3 * n + 1`) and counting the steps until `n` becomes 1.
- Create a list of pairs or a 2D array to store `(number, power_value)` for each integer from `lo` to `hi`.
- Iterate from `lo` to `hi`. In each iteration, for the current number `i`, call `getPower(i)` and store the pair `(i, getPower(i))`.
- Use a custom comparator to sort the list of pairs. The comparator should:
  - First, compare pairs based on their power values in ascending order.
  - If power values are equal, compare them based on the original numbers in ascending order.
- After sorting, the element at index `k-1` is the k-th smallest. Return its original number.

## Memoization with Sorting
This approach improves upon the brute-force method by optimizing the power calculation. The Collatz sequence for different starting numbers often shares common subproblems (e.g., many sequences eventually reach 16, 8, 4, 2, 1). We can avoid re-calculating the power for these common numbers by using memoization (a form of dynamic programming). We use a cache (like a `HashMap`) to store the power value of a number once it's computed.
**Time:** O(T_power + N log N), where `N = hi - lo + 1`. `T_power` is the total time to compute the power values for all numbers and their intermediate steps. Since each power value is computed only once, this is much faster than the brute-force calculation. The dominant part of the complexity is often the sorting step, `O(N log N)`. · **Space:** O(N + M), where `N` is for storing the pairs and `M` is the number of unique integers encountered during all power calculations for the memoization cache. `M` can be larger than `hi`.
**Pros:** Significantly faster power calculation due to caching.; Reduces the overall runtime compared to the brute-force approach.
**Cons:** Still requires sorting the entire list of `N` elements, which is unnecessary if we only need the k-th element.; The memoization cache can grow large if the intermediate numbers in the Collatz sequences are large, increasing space complexity.
### Explanation
The key enhancement here is a cache that prevents redundant computations. We create a map to act as our memoization table. The `getPower` function is modified to first check this map before performing any calculation. If a value is found, it's returned immediately. Otherwise, the power is calculated recursively, and the result is stored in the map for future use. This significantly speeds up the first phase of the algorithm. The rest of the logic—storing pairs, sorting, and returning the k-th element—remains unchanged.

```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    private Map<Integer, Integer> memo = new HashMap<>();

    public int getKth(int lo, int hi, int k) {
        List<int[]> pairs = new ArrayList<>();
        for (int i = lo; i <= hi; i++) {
            pairs.add(new int[]{i, getPower(i)});
        }

        Collections.sort(pairs, (a, b) -> {
            if (a[1] != b[1]) {
                return Integer.compare(a[1], b[1]);
            } else {
                return Integer.compare(a[0], b[0]);
            }
        });

        return pairs.get(k - 1)[0];
    }

    private int getPower(int n) {
        if (n == 1) {
            return 0;
        }
        if (memo.containsKey(n)) {
            return memo.get(n);
        }

        int power;
        if (n % 2 == 0) {
            power = 1 + getPower(n / 2);
        } else {
            power = 1 + getPower(3 * n + 1);
        }
        
        memo.put(n, power);
        return power;
    }
}
```
### Algorithm
- Initialize a cache, for instance, a `HashMap<Integer, Integer>`, to store computed power values.
- Create a recursive helper function `getPower(n, memo)` that:
  - Checks if `n` is 1 (base case, power is 0).
  - Checks if the power of `n` is already in the cache. If so, returns the cached value.
  - If not, it calculates the power by applying the rule (`n/2` or `3n+1`) and making a recursive call: `1 + getPower(next_n, memo)`.
  - Stores the newly computed power in the cache before returning it.
- The main logic remains the same as the brute-force approach: iterate from `lo` to `hi`, get the power for each number using the memoized function, store the `(number, power)` pairs, and sort them.
- Return the number from the k-th pair.

## Memoization with a Max-Heap
This approach further optimizes the solution by avoiding a full sort. Since we only need the k-th smallest element, we don't need to know the complete sorted order of all `N` elements. We can use a selection algorithm. A max-heap (or a `PriorityQueue` configured as one) of size `k` is a perfect data structure for this. We iterate through the numbers, maintaining a heap of the `k` "smallest" elements seen so far.
**Time:** O(T_power + N log k), where `N = hi - lo + 1`. We iterate through `N` numbers, and each heap operation (offer/poll) takes `O(log k)` time. This is more efficient than `O(N log N)` when `k` is significantly smaller than `N`. · **Space:** O(k + M), where `k` is the size of the heap and `M` is the size of the memoization cache. This is better than the sorting approaches in terms of space (excluding the cache) as we only need to store `k` elements instead of `N`.
**Pros:** Most efficient approach, especially when `k` is small compared to `N`.; Avoids an unnecessary full sort, leading to better time complexity.; Space efficient as it only stores `k` elements in the heap (plus the memoization cache).
**Cons:** Slightly more complex to implement than a simple sort due to the use of a custom-comparator priority queue.
### Explanation
This method combines efficient power calculation with an efficient selection algorithm. Instead of collecting all pairs and sorting them, we process them one by one and maintain a max-heap of size `k`. The heap is ordered such that the element with the highest power (or highest number in case of a tie) is at the top. For each number in the range `[lo, hi]`, we calculate its power and push the `(number, power)` pair onto the heap. If the heap's size exceeds `k`, we pop the top element. This ensures the heap always holds the `k` elements with the smallest power values encountered so far. After checking all numbers, the top of the heap is precisely the k-th element we are looking for.

```java
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

class Solution {
    private Map<Integer, Integer> memo = new HashMap<>();

    public int getKth(int lo, int hi, int k) {
        // Max-heap to store pairs [number, power]
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> {
            if (a[1] != b[1]) {
                return Integer.compare(b[1], a[1]); // Sort by power descending
            } else {
                return Integer.compare(b[0], a[0]); // Then by number descending
            }
        });

        for (int i = lo; i <= hi; i++) {
            int power = getPower(i);
            maxHeap.offer(new int[]{i, power});
            if (maxHeap.size() > k) {
                maxHeap.poll();
            }
        }

        return maxHeap.peek()[0];
    }

    private int getPower(int n) {
        if (n == 1) return 0;
        if (memo.containsKey(n)) return memo.get(n);
        
        int power;
        if (n % 2 == 0) {
            power = 1 + getPower(n / 2);
        } else {
            power = 1 + getPower(3 * n + 1);
        }
        
        memo.put(n, power);
        return power;
    }
}
```
### Algorithm
- Use the same memoized `getPower` function from the previous approach to efficiently calculate power values.
- Initialize a max-heap (`PriorityQueue`) of size `k`. The comparator for the heap should place the "largest" elements at the top. "Largest" is defined first by power value (descending), then by the number itself (descending).
- Iterate through the numbers from `lo` to `hi`. For each number `i`:
  - Calculate its power `p = getPower(i)`.
  - Add the pair `(i, p)` to the max-heap.
  - If the heap's size grows larger than `k`, remove the top element (the current "largest" among the `k+1` elements).
- After iterating through all numbers, the heap contains the `k` smallest elements from the range. The element at the top of the heap is the k-th smallest element.
- Return the number component of the pair at the top of the heap (`heap.peek()[0]`).

# Solutions
### Java

```java
class Solution {
public
  int getKth(int lo, int hi, int k) {
    Integer[] nums = new Integer[hi - lo + 1];
    for (int i = lo; i <= hi; ++i) {
      nums[i - lo] = i;
    }
    Arrays.sort(
        nums, (a, b)->{
          int fa = f(a), fb = f(b);
          return fa == fb ? a - b : fa - fb;
        });
    return nums[k - 1];
  }
private
  int f(int x) {
    int ans = 0;
    for (; x != 1; ++ans) {
      if (x % 2 == 0) {
        x /= 2;
      } else {
        x = x * 3 + 1;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int getKth(int lo, int hi, int k) {
    auto f = [](int x) {
      int ans = 0;
      for (; x != 1; ++ans) {
        if (x % 2 == 0) {
          x /= 2;
        } else {
          x = 3 * x + 1;
        }
      }
      return ans;
    };
    vector<int> nums;
    for (int i = lo; i <= hi; ++i) {
      nums.push_back(i);
    }
    sort(nums.begin(), nums.end(), [&](int x, int y) {
      int fx = f(x), fy = f(y);
      if (fx != fy) {
        return fx < fy;
      } else {
        return x < y;
      }
    });
    return nums[k - 1];
  }
};

```

### Python

```python
@ cache def f ( x : int ) -> int : ans = 0 while x != 1 : if x % 2 == 0 : x //= 2 else : x = 3 * x + 1 ans += 1 return ans class Solution : def getKth ( self , lo : int , hi : int , k : int ) -> int : return sorted ( range ( lo , hi + 1 ), key = f )[ k - 1 ]
```