Sort Integers by The Power Value
MedPrompt
The power of an integer x is defined as the number of steps needed to transform x into 1 using the following steps:
- if
xis even thenx = x / 2 - if
xis odd thenx = 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 <= 10001 <= k <= hi - lo + 1
Approaches
3 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Create a helper function
getPower(n)that calculates the power of an integernby simulating the process described (ifnis even,n = n / 2; ifnis odd,n = 3 * n + 1) and counting the steps untilnbecomes 1. - Create a list of pairs or a 2D array to store
(number, power_value)for each integer fromlotohi. - Iterate from
lotohi. In each iteration, for the current numberi, callgetPower(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-1is the k-th smallest. Return its original number.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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 ...).
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.
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
nis 1 (base case, power is 0). - Checks if the power of
nis already in the cache. If so, returns the cached value. - If not, it calculates the power by applying the rule (
n/2or3n+1) and making a recursive call:1 + getPower(next_n, memo). - Stores the newly computed power in the cache before returning it.
- Checks if
- The main logic remains the same as the brute-force approach: iterate from
lotohi, 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.
Walkthrough
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.
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; }}Complexity
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`.
Trade-offs
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
Nelements, 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.
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.
Algorithm
- Use the same memoized
getPowerfunction from the previous approach to efficiently calculate power values. - Initialize a max-heap (
PriorityQueue) of sizek. 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
lotohi. For each numberi:- 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 thek+1elements).
- Calculate its power
- After iterating through all numbers, the heap contains the
ksmallest 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]).
Walkthrough
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.
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; }}Complexity
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`.
Trade-offs
Pros
Most efficient approach, especially when
kis small compared toN.Avoids an unnecessary full sort, leading to better time complexity.
Space efficient as it only stores
kelements 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.
Solutions
Solution
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; }}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]; }};@ 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 ]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.