Sort Integers by The Power Value
Problem
The power of an integer x is the number of steps to reach 1 using: if x is even, x = x / 2; if x is odd, x = 3·x + 1. Given lo, hi, and k, sort every integer in [lo, hi] by ascending power value (ties broken by ascending value) and return the k-th element.
lo = 12, hi = 15, k = 213lo = 7, hi = 11, k = 47def getKth(lo, hi, k):
memo = {1: 0}
def power(x):
if x in memo:
return memo[x]
nxt = x // 2 if x % 2 == 0 else 3 * x + 1
memo[x] = 1 + power(nxt)
return memo[x]
nums = list(range(lo, hi + 1))
nums.sort(key=lambda x: (power(x), x))
return nums[k - 1]function getKth(lo, hi, k) {
const memo = new Map([[1, 0]]);
function power(x) {
if (memo.has(x)) return memo.get(x);
const nxt = x % 2 === 0 ? x / 2 : 3 * x + 1;
memo.set(x, 1 + power(nxt));
return memo.get(x);
}
const nums = [];
for (let x = lo; x <= hi; x++) nums.push(x);
nums.sort((a, b) => power(a) - power(b) || a - b);
return nums[k - 1];
}Map<Integer, Integer> memo = new HashMap<>();
int power(int x) {
if (x == 1) return 0;
if (memo.containsKey(x)) return memo.get(x);
long nxt = (x % 2 == 0) ? x / 2 : 3L * x + 1;
int p = 1 + power((int) nxt);
memo.put(x, p);
return p;
}
int getKth(int lo, int hi, int k) {
List<Integer> nums = new ArrayList<>();
for (int x = lo; x <= hi; x++) nums.add(x);
nums.sort((a, b) -> power(a) != power(b) ? power(a) - power(b) : a - b);
return nums.get(k - 1);
}unordered_map<int, int> memo;
int power(int x) {
if (x == 1) return 0;
if (memo.count(x)) return memo[x];
long long nxt = (x % 2 == 0) ? x / 2 : 3LL * x + 1;
int p = 1 + power((int) nxt);
memo[x] = p;
return p;
}
int getKth(int lo, int hi, int k) {
vector<int> nums;
for (int x = lo; x <= hi; x++) nums.push_back(x);
sort(nums.begin(), nums.end(), [&](int a, int b) {
return power(a) != power(b) ? power(a) < power(b) : a < b;
});
return nums[k - 1];
}Explanation
This problem has two independent phases: compute a power value for every integer in the range, then sort the integers by that value.
The power of x is its Collatz step count: repeatedly halve even numbers and apply 3x + 1 to odd numbers, counting how many steps it takes to reach 1. Computed naively, two nearby numbers redo a lot of the same work because their Collatz chains overlap.
That overlap is exactly what memoization exploits. We cache power(x) in a dictionary keyed by x with the base case power(1) = 0. Each call follows one step to nxt, recurses, and stores 1 + power(nxt). Once a value is cached, any later chain that lands on it returns instantly — so the whole range is effectively one shared computation.
With every power known, we sort the integers using the comparison key (power(x), x): primarily by ascending power, and by ascending value to break ties. A stable sort on this composite key gives the required ordering.
Finally we return the element at index k - 1 (converting the 1-based rank k to a 0-based index). Example: for lo = 12, hi = 15, k = 2 the powers are 9, 9, 17, 17, so the sorted order is [12, 13, 14, 15] and the answer is 13.