Sort Integers by The Power Value

Medium
427.

Sort Integers by The Power Value

Sort Integers by The Power Value is a medium coding problem on dynamic programming, sorting and memoization, asked in Amazon and Google interviews.

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 <= 20000
  • hi - lo <= 40
  • 1 <= k <= hi - lo + 1
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} lo
 * @param {number} hi
 * @param {number} k
 * @return {number}
 */
var getKth = function(lo, hi, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 20000
  • hi - lo <= 40
  • 1 <= k <= hi - lo + 1

Hints for Sort Integers by The Power Value

  1. Hint 1

    Compute each value's power by simulating the Collatz steps — the sequence always terminates in this range.

  2. Hint 2

    Then sort by (power, value) and index into the result.

  3. 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

  1. Define power(x) by simulating halving / 3x + 1 until 1.
  2. Sort lo..hi by (power, value) and return index k - 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 power if the same values recur — intermediate values can exceed hi.

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