Abstract / Summary

Sort numbers by the highest power of two dividing each number then by the number value.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 72% (100k+ submissions).

Typical patterns to solve this problem:

• Dynamic Programming
• Memoization
• Sorting

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided Solution class implements a method getKth that returns the integer within the inclusive range [lo, hi] whose “power value” ranks k-th when the values are ordered by their power. The power of a number is defined by the length of the Collatz-like sequence that reduces the number to 1, counting each transformation step. The algorithm builds a min-heap keyed by these power values and extracts the smallest elements until the desired rank is reached.

Core Functionality

The entry point is the getKth method, which receives three integer arguments: the lower bound lo, the upper bound hi, and the rank k. Inside the method a nested helper function power computes the power value for any positive integer. The method then creates a list of tuples (power(i), i) for every i in the range, transforms the list into a heap, discards the first k-1 elements, and finally returns the integer component of the heap’s root.

def getKth(self, lo: int, hi: int, k: int) -> int:
    @cache
    def power(n):
        ...
    h = []
    for i in range(lo, hi + 1):
        h.append((power(i), i))
    heapify(h)
    for _ in range(k - 1):
        heappop(h)
    return h[0][1]

Recursive Power Computation

The nested power function determines the number of steps required to reach 1 using the following rules: if the current value is even, it is halved; if odd, it is transformed to 3 * n + 1. Each recursive call adds one to the step count. The base case occurs when n equals 1, returning a count of 0. The function is decorated with @cache, which memoizes previously computed results, allowing repeated calls for the same argument to retrieve the stored value instantly.

@cache
def power(n):
    if n == 1:
        return 0
    if n % 2 == 0:
        return 1 + power(n // 2)
    else:
        return 1 + power(3 * n + 1)

Heap Construction

A list h is populated with tuples where the first element is the power of a number and the second element is the number itself. This ordering ensures that the heap property is based on the power value, while the original integer is retained for final retrieval. The standard library function heapify converts the list into a valid min-heap in linear time.

h = []
for i in range(lo, hi + 1):
    h.append((power(i), i))
heapify(h)

Selection of the kth Element

After the heap is built, the algorithm removes the smallest element k-1 times using heappop. Each removal discards the current minimum power entry, effectively advancing the rank. The element that remains at the root of the heap after these removals corresponds to the k-th smallest power value. The method returns the integer component of that tuple.

for _ in range(k - 1):
    heappop(h)
return h[0][1]

Edge Cases

The implementation gracefully handles the situation where lo equals hi. In that case the loop that populates the heap runs once, the heap contains a single tuple, and the subsequent for loop that discards elements executes zero times because k-1 equals zero. The method then returns the sole number, satisfying the request for the first (and only) rank.

When k is 1, the removal loop is bypassed entirely, and the root of the heap after heapify directly yields the number with the smallest power.

The memoization in power also covers the edge case where the same intermediate value appears in multiple Collatz sequences. By caching the result of each distinct n, the function avoids redundant recursion for values that recur across different starting numbers.

Performance Optimizations

The use of @cache on the recursive power function is a significant optimization. Collatz sequences often intersect; caching ensures that once the power of a particular intermediate value is known, any subsequent encounter retrieves the result in constant time rather than recomputing the entire sub-sequence.

Heap construction via heapify is performed on the complete list of (power, number) pairs, which is more efficient than inserting each element individually. This approach builds the heap in a single pass, leveraging the underlying algorithm that rearranges the list in place.

The algorithm discards only the first k-1 elements from the heap, avoiding the need to sort the entire range. By relying on the heap’s ability to provide the smallest element in logarithmic time per removal, the method limits work to the necessary portion of the ordered sequence.

Overall, the combination of memoization, bulk heap creation, and targeted extraction yields a solution that scales well for moderate ranges while minimizing redundant calculations.

Imagine you have a giant collection of number toys. Some numbers are like energetic bunnies that hop around a lot before they finally settle down at the number one, while others get there much faster. To figure out which numbers stay active for longer, this little program creates a special game called power. When you give it any number, it keeps track of how many tiny steps that number takes to reach one. If the number is even, it gets cut in half, and if it is odd, it gets multiplied by three and adds one to stay busy.

Once the program knows how many steps every number from your starting point to your ending point takes, it puts them all into a tidy pile. It sorts the pile based on those step counts so the numbers that move the least are right on top. Then, the program removes the top numbers from the pile over and over again until it finds the specific one that holds the spot you were looking for. It is like organizing your toys by how much they wiggle and then picking the one that wiggles just the right amount for your turn.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: loglinear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python		Java					TS
	WalkCCC	C++	Python		Java
	leetcode.ca	C++	Python		Java			Go	Rust	TS
	Progiez	C++	Python		Java
github	BigEggStudy						C#
	black-shadows	C++
	charles-wangkai				Java
	everthis			JS
	fartem					Ruby
	fsq	C++
	JoshCrozier			JS
	keineahnung2345	C++
	lkwq007		Python
	lzl124631x	C++
	trung-hn		Python
	varunu28				Java
	YuriSpiridonov		Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
fsq	C++
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
lzl124631x	C++
trung-hn	Python
varunu28	Java
YuriSpiridonov	Python

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality