Sort integers by the power value

Dynamic Programming Memoization Sorting

71.6% acceptance

Feb 25, 2026

1511

121

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.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn get_kth(lo: i32, hi: i32, k: i32) -> i32 {
    fn power(mut x: i32) -> i32 {
      let mut steps = 0;
      while x != 1 {
        if x % 2 == 0 { x /= 2; } else { x = 3 * x + 1; }
        steps += 1;
      }
      steps
    }
    let mut arr: Vec<i32> = (lo..=hi).collect();
    arr.sort_by_key(|&x| (power(x), x));
    arr[(k - 1) as usize]
  }
}