Sort Integers by The Power Value: Collatz Memoization

The power of an integer x is defined as the number of steps needed to transform x into 1 using the Collatz sequence: if x is even, replace it with x / 2. If x is odd, replace it with 3 * x + 1. Given integers lo, hi, and k, sort all integers in the range [lo, hi] by their power value. If two numbers have the same power, sort them by value (ascending). Return the kth number in the sorted list.

This is LeetCode 1387: Sort Integers by The Power Value, and it is a great exercise in combining memoized recursion with custom sorting.

Why this problem matters

Computing the Collatz chain for a single number is easy. Computing it for an entire range is where things get interesting. Many numbers share overlapping tails in their chains. The number 7 passes through 22, 11, 34, 17, and so on. The number 11 hits the same sequence starting from 34. If you compute the power of 7 first, you have already done most of the work for 11.

This is a natural application of memoization. By caching the power of every number you encounter along the way, you avoid recomputing shared suffixes. Combine that with a custom sort key, and the problem falls into place.

The key insight

Use a cache (dictionary or lru_cache) to store the power of every number you compute. When you compute power(7), you walk through 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1. Each of those intermediate values gets its own power computed along the way. Later, when you need power(11) or power(22), you hit the cache immediately.

Once you have the power for every number in [lo, hi], sort by (power, number) and return the element at index k - 1.

The solution

from functools import lru_cache

def getKth(lo, hi, k):
    @lru_cache(maxsize=None)
    def power(x):
        if x == 1:
            return 0
        if x % 2 == 0:
            return 1 + power(x // 2)
        return 1 + power(3 * x + 1)

    nums = list(range(lo, hi + 1))
    nums.sort(key=lambda x: (power(x), x))
    return nums[k - 1]

The power function is a direct translation of the Collatz rules. The @lru_cache decorator handles memoization automatically. You build the list of numbers, sort by (power, number), and index into the result.

Visual walkthrough

The walkthrough uses lo=7, hi=11, k=2. After computing the power of each number and sorting, the second element is 10 with a power of 6.

Complexity analysis

Here n = hi - lo + 1 (the size of the range) and s is the average length of a Collatz chain. The O(n * s) term covers the total work to compute all power values, though in practice memoization makes this significantly faster because chains overlap heavily. The O(n log n) term is the sort. Space is dominated by the memoization cache, which stores the power for every intermediate number encountered.

For the given constraints (lo and hi up to 1000), this runs comfortably fast.

The building blocks

1. Memoized recursive computation

The core technique is memoizing a recursive function where subproblems overlap. This is the same idea behind top-down dynamic programming.

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

Without memoization, computing the power for a range of numbers would repeat enormous amounts of work. With it, each unique number is computed exactly once. This is the same pattern you use in Climbing Stairs, Fibonacci, and any other problem with overlapping subproblems.

2. Custom sort key

Python's sort accepts a key function that determines the sort order. By returning a tuple (power(x), x), you sort primarily by power and break ties by the number itself.

nums.sort(key=lambda x: (power(x), x))

This is a clean, Pythonic way to express multi-criteria sorting. The same technique applies whenever you need to sort by a computed property with a tiebreaker.

Edge cases

• Single element range: when lo == hi, the answer is always lo regardless of k (which must be 1).
• Power of 1: the number 1 has power 0. If 1 is in the range, it always comes first in the sorted order.
• Powers of 2: numbers like 2, 4, 8, 16 have very short chains (they just halve down to 1). They tend to appear early in the sorted result.
• Large chains: some small numbers produce surprisingly long Collatz chains. The number 9 takes 19 steps. Memoization prevents this from becoming a performance issue.
• Tie-breaking: when two numbers have the same power, the smaller number comes first. Make sure your sort key includes the number itself as the second element.

From understanding to recall

You have seen how memoized Collatz computation and custom sorting combine to solve this problem. The two building blocks, memoized recursion and tuple-based sort keys, are both patterns you will encounter repeatedly. The Collatz sequence itself is a well-known mathematical curiosity, but the real skill here is recognizing when a recursive computation has overlapping subproblems and reaching for a cache.

Spaced repetition helps you internalize these patterns so they become second nature. Instead of re-deriving the approach each time, you will recognize the structure immediately: "recursive function with shared subproblems, memoize it, then sort by the computed values." That recognition is what makes interview problems feel familiar rather than novel.

Related posts

• Climbing Stairs - The classic introduction to memoized recursion and overlapping subproblems
• House Robber - Another memoized DP problem where decisions at each step depend on previous computations
• Decode Ways - Memoized recursion over a sequence with overlapping substructure

CodeBricks turns pattern recognition into a repeatable skill. Each building block you drill, whether it is memoized recursion, custom sorting, or Collatz-style chain computation, makes the next problem faster to solve.