Sort Integers by The Power Value
MediumUpdated: Sep 1, 2025
Practice on:
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
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.
Examples
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
Solution
Method 1 - Memoization with Sorting
Intuition
Calculate the power (Collatz conjecture steps) for each number in the range using memoization to avoid recomputation, then sort by power value with number as tiebreaker.
Approach
- Use memoization to cache power values to avoid recalculating
- For each number in range [lo, hi], calculate its power value
- Create pairs of (number, power) and sort by power first, then by number
- Return the k-th element (1-indexed)
Code
C++
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;
class Solution {
private:
unordered_map<int, int> memo;
int getPower(int x) {
if (x == 1) return 0;
if (memo.find(x) != memo.end()) return memo[x];
int original = x;
int steps = 0;
while (x != 1 && memo.find(x) == memo.end()) {
if (x % 2 == 0) {
x = x / 2;
} else {
x = 3 * x + 1;
}
steps++;
}
// x is either 1 or found in memo
int totalSteps = steps + (x == 1 ? 0 : memo[x]);
// Backtrack and memoize
x = original;
for (int i = steps; i > 0; i--) {
memo[x] = totalSteps - (steps - i);
if (x % 2 == 0) {
x = x / 2;
} else {
x = 3 * x + 1;
}
}
return memo[original];
}
public:
int getKth(int lo, int hi, int k) {
vector<pair<int, int>> nums;
for (int i = lo; i <= hi; i++) {
nums.push_back({getPower(i), i});
}
sort(nums.begin(), nums.end());
return nums[k - 1].second;
}
};
Go
func getKth(lo int, hi int, k int) int {
memo := make(map[int]int)
var getPower func(int) int
getPower = func(x int) int {
if x == 1 {
return 0
}
if val, exists := memo[x]; exists {
return val
}
original := x
steps := 0
for x != 1 {
if _, exists := memo[x]; exists {
break
}
if x%2 == 0 {
x = x / 2
} else {
x = 3*x + 1
}
steps++
}
totalSteps := steps
if x != 1 {
totalSteps += memo[x]
}
// Backtrack and memoize
x = original
for i := steps; i > 0; i-- {
memo[x] = totalSteps - (steps - i)
if x%2 == 0 {
x = x / 2
} else {
x = 3*x + 1
}
}
return memo[original]
}
type pair struct {
power int
num int
}
var nums []pair
for i := lo; i <= hi; i++ {
nums = append(nums, pair{getPower(i), i})
}
sort.Slice(nums, func(i, j int) bool {
if nums[i].power == nums[j].power {
return nums[i].num < nums[j].num
}
return nums[i].power < nums[j].power
})
return nums[k-1].num
}
Java
import java.util.*;
class Solution {
private Map<Integer, Integer> memo = new HashMap<>();
private int getPower(int x) {
if (x == 1) return 0;
if (memo.containsKey(x)) return memo.get(x);
int original = x;
int steps = 0;
while (x != 1 && !memo.containsKey(x)) {
if (x % 2 == 0) {
x = x / 2;
} else {
x = 3 * x + 1;
}
steps++;
}
int totalSteps = steps + (x == 1 ? 0 : memo.get(x));
// Backtrack and memoize
x = original;
for (int i = steps; i > 0; i--) {
memo.put(x, totalSteps - (steps - i));
if (x % 2 == 0) {
x = x / 2;
} else {
x = 3 * x + 1;
}
}
return memo.get(original);
}
public int getKth(int lo, int hi, int k) {
List<int[]> nums = new ArrayList<>();
for (int i = lo; i <= hi; i++) {
nums.add(new int[]{getPower(i), i});
}
nums.sort((a, b) -> {
if (a[0] == b[0]) return Integer.compare(a[1], b[1]);
return Integer.compare(a[0], b[0]);
});
return nums.get(k - 1)[1];
}
}
Kotlin
class Solution {
private val memo = mutableMapOf<Int, Int>()
private fun getPower(x: Int): Int {
if (x == 1) return 0
if (memo.containsKey(x)) return memo[x]!!
val original = x
var current = x
var steps = 0
while (current != 1 && !memo.containsKey(current)) {
current = if (current % 2 == 0) {
current / 2
} else {
3 * current + 1
}
steps++
}
val totalSteps = steps + if (current == 1) 0 else memo[current]!!
// Backtrack and memoize
current = original
for (i in steps downTo 1) {
memo[current] = totalSteps - (steps - i)
current = if (current % 2 == 0) {
current / 2
} else {
3 * current + 1
}
}
return memo[original]!!
}
fun getKth(lo: Int, hi: Int, k: Int): Int {
val nums = mutableListOf<Pair<Int, Int>>()
for (i in lo..hi) {
nums.add(Pair(getPower(i), i))
}
nums.sortWith { a, b ->
when {
a.first != b.first -> a.first.compareTo(b.first)
else -> a.second.compareTo(b.second)
}
}
return nums[k - 1].second
}
}
Python
def getKth(lo: int, hi: int, k: int) -> int:
memo = {}
def get_power(x):
if x == 1:
return 0
if x in memo:
return memo[x]
original = x
steps = 0
while x != 1 and x not in memo:
if x % 2 == 0:
x = x // 2
else:
x = 3 * x + 1
steps += 1
total_steps = steps + (0 if x == 1 else memo[x])
# Backtrack and memoize
x = original
for i in range(steps, 0, -1):
memo[x] = total_steps - (steps - i)
if x % 2 == 0:
x = x // 2
else:
x = 3 * x + 1
return memo[original]
nums = []
for i in range(lo, hi + 1):
nums.append((get_power(i), i))
nums.sort()
return nums[k - 1][1]
Rust
use std::collections::HashMap;
pub fn get_kth(lo: i32, hi: i32, k: i32) -> i32 {
let mut memo: HashMap<i32, i32> = HashMap::new();
fn get_power(x: i32, memo: &mut HashMap<i32, i32>) -> i32 {
if x == 1 {
return 0;
}
if let Some(&power) = memo.get(&x) {
return power;
}
let original = x;
let mut current = x;
let mut steps = 0;
while current != 1 && !memo.contains_key(¤t) {
if current % 2 == 0 {
current = current / 2;
} else {
current = 3 * current + 1;
}
steps += 1;
}
let total_steps = steps + if current == 1 { 0 } else { memo[¤t] };
// Backtrack and memoize
current = original;
for i in (1..=steps).rev() {
memo.insert(current, total_steps - (steps - i));
if current % 2 == 0 {
current = current / 2;
} else {
current = 3 * current + 1;
}
}
memo[&original]
}
let mut nums = Vec::new();
for i in lo..=hi {
nums.push((get_power(i, &mut memo), i));
}
nums.sort();
nums[(k - 1) as usize].1
}
TypeScript
function getKth(lo: number, hi: number, k: number): number {
const memo = new Map<number, number>();
function getPower(x: number): number {
if (x === 1) return 0;
if (memo.has(x)) return memo.get(x)!;
const original = x;
let current = x;
let steps = 0;
while (current !== 1 && !memo.has(current)) {
if (current % 2 === 0) {
current = current / 2;
} else {
current = 3 * current + 1;
}
steps++;
}
const totalSteps = steps + (current === 1 ? 0 : memo.get(current)!);
// Backtrack and memoize
current = original;
for (let i = steps; i > 0; i--) {
memo.set(current, totalSteps - (steps - i));
if (current % 2 === 0) {
current = current / 2;
} else {
current = 3 * current + 1;
}
}
return memo.get(original)!;
}
const nums: [number, number][] = [];
for (let i = lo; i <= hi; i++) {
nums.push([getPower(i), i]);
}
nums.sort((a, b) => {
if (a[0] === b[0]) return a[1] - b[1];
return a[0] - b[0];
});
return nums[k - 1][1];
}
Complexity
- ⏰ Time complexity:
O(n * m + n log n)where n = hi - lo + 1 (range size), m = average steps for Collatz sequence - 🧺 Space complexity:
O(n + cache_size)for storing pairs and memoization cache