Sort Integers by The Power Value — Problem & Solution
Sort Integers by The Power Value solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Sort Integers by The Power Value is a medium coding problem on dynamic programming, sorting and memoization, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Dynamic Programming, Sorting, Memoization
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
The power of an integer x is the number of steps needed to reach 1 under the rule: if x is even, halve it; if x is odd, replace it with 3x + 1.
Sort the integers in the range [lo, hi] by increasing power, breaking ties by the value itself, and return the k-th value of that ordering (1-indexed).
Example 1
Input: lo = 12, hi = 15, k = 2
Output: 13
Explanation: The powers are 9, 9, 6 and 17, so the order is 13, 12, 15, 14.
Example 2
Input: lo = 7, hi = 11, k = 4
Output: 7
Example 3
Input: lo = 1, hi = 1, k = 1
Output: 1
Constraints
1 <= lo <= hi <= 20000hi - lo <= 401 <= k <= hi - lo + 1
Hints for Sort Integers by The Power Value
Hint 1
Compute each value's power by simulating the Collatz steps — the sequence always terminates in this range.
Hint 2
Then sort by (power, value) and index into the result.
Hint 3
Memoising the powers pays off when the same values recur across queries.
How to solve Sort Integers by The Power Value
Compute each value's Collatz step count, sort the range by (power, value), and pick the k-th.
Approach
- Define
power(x)by simulating halving /3x + 1until 1. - Sort
lo..hiby(power, value)and return indexk - 1.
Why it works
The ordering is fully specified by the composite key, and the Collatz sequence terminates for every value in range.
Complexity
- Time —
O((hi - lo) · steps + (hi - lo) log(hi - lo)) - Space —
O(hi - lo)
Pitfalls
- Memoise
powerif the same values recur — intermediate values can exceedhi.
Reference solution
Python
def getKth(lo: int, hi: int, k: int) -> int:
def power(x):
steps = 0
while x != 1:
x = x // 2 if x % 2 == 0 else 3 * x + 1
steps += 1
return steps
return sorted(range(lo, hi + 1), key=lambda v: (power(v), v))[k - 1]Java
private static int collatzPower(int x) {
int steps = 0;
long v = x;
while (v != 1) {
v = v % 2 == 0 ? v / 2 : 3 * v + 1;
steps++;
}
return steps;
}
public static int getKth(int lo, int hi, int k) {
Integer[] values = new Integer[hi - lo + 1];
for (int i = 0; i < values.length; i++) values[i] = lo + i;
Arrays.sort(values, (a, b) -> {
int pa = collatzPower(a), pb = collatzPower(b);
return pa != pb ? pa - pb : a - b;
});
return values[k - 1];
}C++
static int collatzPower(int x) {
int steps = 0;
long long v = x;
while (v != 1) {
v = v % 2 == 0 ? v / 2 : 3 * v + 1;
steps++;
}
return steps;
}
int getKth(int lo, int hi, int k) {
vector<int> values;
for (int v = lo; v <= hi; v++) values.push_back(v);
sort(values.begin(), values.end(), [](int a, int b) {
int pa = collatzPower(a), pb = collatzPower(b);
if (pa != pb) return pa < pb;
return a < b;
});
return values[k - 1];
}JavaScript
var getKth = function(lo, hi, k) {
const power = function(x) {
let steps = 0;
let v = x;
while (v !== 1) {
v = v % 2 === 0 ? v / 2 : 3 * v + 1;
steps++;
}
return steps;
};
const values = [];
for (let v = lo; v <= hi; v++) values.push(v);
values.sort(function(a, b) {
const pa = power(a), pb = power(b);
return pa !== pb ? pa - pb : a - b;
});
return values[k - 1];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 402 dynamic programming problems · the whole catalogue
Learn the technique: Dynamic Programming · Sorting Algorithms