Problem Description

You are given three integers: lo, hi, and k. Your task is to sort all integers in the range [lo, hi] by their "power value" and return the k-th integer in this sorted list.

The "power value" of an integer x is defined as the number of steps required to transform x into 1 using the following process:

• If x is even, replace x with x / 2.
• If x is odd, replace x with 3 * x + 1.
• Repeat the process until x becomes 1.

You must sort the numbers from lo to hi (inclusive) by their power values in ascending order. If two numbers have the same power value, sort them by their integer value in ascending order. Return the k-th integer (1-indexed) from this sorted list.

Constraints:

• Each input has exactly one valid solution.
• Each integer in the range is unique and must be used exactly once.
• 1 ≤ lo ≤ hi ≤ 1000
• 1 ≤ k ≤ hi - lo + 1

Thought Process

At first glance, the problem asks us to sort a range of numbers based on a custom metric ("power value") derived from the Collatz sequence rules. A brute-force approach would be to compute the power value for every number in the range, sort them, and return the k-th smallest. However, since calculating the power value involves repeated computation for the same intermediate numbers, we can optimize by caching results (memoization).

The key insight is to:

• Efficiently compute the power value for each number using recursion and memoization.
• Pair each number with its computed power value.
• Sort the pairs first by power value, then by the number itself.
• Return the k-th element.

Solution Approach

Let's break down the solution step-by-step:

1. Compute Power Values:
   • For each integer x in the range [lo, hi], compute its power value.
   • Use recursion to follow the Collatz rules, counting steps until reaching 1.
   • Implement memoization (using a hash map/dictionary) to avoid recomputing power values for numbers we've seen before.
2. Create a List of Pairs:
   • Store each number along with its power value in a list of tuples or objects.
3. Sort the List:
   • Sort the list first by power value (ascending), then by the number itself (ascending) in case of ties.
4. Return the k-th Element:
   • Since the list is 0-indexed, return the number at position k-1.

This method ensures we only compute each power value once, sort efficiently, and select the correct output.

Example Walkthrough

Input: lo = 12, hi = 15, k = 2

Let's walk through the steps:

1. Compute power values:
   • 12: 12 → 6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1 (9 steps)
   • 13: 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 (9 steps)
   • 14: 14 → 7 → 22 → 11 → 34 → 17 → 52 → 26 → 13 → ... (eventually reaches 1 in 17 steps)
   • 15: 15 → 46 → 23 → 70 → 35 → 106 → ... (eventually reaches 1 in 17 steps)
2. Pair numbers with power values:
   • (12, 9), (13, 9), (14, 17), (15, 17)
3. Sort:
   • Sorted by power value, then number: (12, 9), (13, 9), (14, 17), (15, 17)
4. Find the k-th element (k=2):
   • Second element is 13.

Time and Space Complexity

Brute-force approach:

• For each number in [lo, hi], compute the power value individually without caching.
• Each computation can take up to O(log n) steps (in practice, much less for n ≤ 1000).
• Sorting takes O(N log N) where N = hi - lo + 1.
• Overall: O(N log N + N * log M), where M is the largest number in the Collatz sequence encountered.

• Each unique number's power value is computed once and cached.
• Subsequent computations for the same number are O(1).
• Sorting remains O(N log N).
• Space for memoization: O(M), where M is the largest number encountered during sequences.
• Overall: O(N log N) time and O(M) space.

Summary

The problem challenges us to sort numbers by a custom "power value" derived from the Collatz sequence. By combining recursion, memoization, and stable sorting, we efficiently compute and order the numbers, ensuring correctness and performance. The approach highlights the power of dynamic programming (memoization) for overlapping subproblems and demonstrates how to adapt sorting to custom criteria in coding interviews.

Code Implementation

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        from functools import lru_cache

        @lru_cache(None)
        def power(x):
            if x == 1:
                return 0
            if x % 2 == 0:
                return 1 + power(x // 2)
            else:
                return 1 + power(3 * x + 1)

        arr = []
        for num in range(lo, hi + 1):
            arr.append((power(num), num))
        arr.sort()
        return arr[k - 1][1]
      

class Solution {
public:
    unordered_map memo;
    int power(int x) {
        if (x == 1) return 0;
        if (memo.count(x)) return memo[x];
        if (x % 2 == 0)
            return memo[x] = 1 + power(x / 2);
        else
            return memo[x] = 1 + power(3 * x + 1);
    }

    int getKth(int lo, int hi, int k) {
        vector> arr;
        for (int i = lo; i <= hi; ++i) {
            arr.push_back({power(i), i});
        }
        sort(arr.begin(), arr.end());
        return arr[k - 1].second;
    }
};
      

class Solution {
    private Map memo = new HashMap<>();
    
    private int power(int x) {
        if (x == 1) return 0;
        if (memo.containsKey(x)) return memo.get(x);
        int res;
        if (x % 2 == 0)
            res = 1 + power(x / 2);
        else
            res = 1 + power(3 * x + 1);
        memo.put(x, res);
        return res;
    }
    
    public int getKth(int lo, int hi, int k) {
        List arr = new ArrayList<>();
        for (int i = lo; i <= hi; ++i) {
            arr.add(new int[]{power(i), i});
        }
        arr.sort((a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0]) : Integer.compare(a[1], b[1]));
        return arr.get(k - 1)[1];
    }
}
      

var getKth = function(lo, hi, k) {
    const memo = new Map();
    function power(x) {
        if (x === 1) return 0;
        if (memo.has(x)) return memo.get(x);
        let res;
        if (x % 2 === 0)
            res = 1 + power(x / 2);
        else
            res = 1 + power(3 * x + 1);
        memo.set(x, res);
        return res;
    }
    let arr = [];
    for (let i = lo; i <= hi; ++i) {
        arr.push([power(i), i]);
    }
    arr.sort((a, b) => a[0] !== b[0] ? a[0] - b[0] : a[1] - b[1]);
    return arr[k - 1][1];
};