1387. Sort Integers by The Power Value

MediumMemoizationDynamic ProgrammingSorting

Problem Description

In this problem, we are introduced to a special mathematical transformation of an integer x, which ultimately reduces x to 1 through a series of steps. These steps consist of halving x if it is even, or replacing x with 3 * x + 1 if it is odd. The "power" of an integer x is defined as the number of these steps required to reduce x to 1.

Given three integers lo, hi, and k, the goal is to find the kth smallest integer in the range [lo, hi] when all the integers within this range are sorted by their power values first (ascending), and by their natural values next (also ascending) if they have the same power value.

Consider an example where lo = 3, hi = 5, and k = 2. Power values for integers 3, 4 and 5 are 7, 2, and 5 respectively. After sorting them by their power values, we get the sequence 4, 5, 3. The second integer in this sequence is 5, which would be the output for these input values.

It's guaranteed in this problem that the power value for any integer x within the range will fit within a 32-bit signed integer, and that x will eventually transform to 1 through the given steps.

Intuition

To solve this problem, we need a function that computes the power of any given number x. The provided solution encapsulates this in a function f(x), which is decorated with @cache to store the results of computation for each unique value of x. This prevents repeated computation and improves efficiency if the same number appears multiple times during the sorting process.

Once we have the function to compute the power of an integer, we can generate all integers within the range [lo, hi] and sort them primarily by the computed power values and secondarily by their natural values in case of ties in power values. This is achieved by passing the custom sorting key f to Python's built-in sorted function. After sorting, we simply return the k-1 indexed element from this sorted list (since lists are zero-indexed in Python).

The solution is quite straightforward:

Compute the power for each number in the range using the f(x) function.
Cache the result each time it's computed to improve efficiency for repeated calculations.
Sort all numbers by their power values, and if there's a tie, by their natural values.
Return the kth number in the sorted sequence.

Learn more about Memoization, Dynamic Programming and Sorting patterns.

Solution Approach

The implementation of the solution breaks down into the creation of a helper function f(x) and using built-in Python features to sort and retrieve the desired kth element.

First, let's discuss the helper function f(x):

Helper Function `f(x)`

The helper function f(x) computes the power of a number x according to the rules given in the problem statement. It initiates a counter (ans) that tracks the number of steps taken to reduce x to 1. Inside a while loop, as long as x is not 1, the function checks if x is even or odd. If it's even, x is divided by 2, otherwise it’s replaced with 3 * x + 1, as described in the problem. The counter is incremented after each operation.

A key optimization implemented here is the use of the @cache decorator. This decorator from the functools module caches the result of the power calculation for each unique input x. Later calls to the f(x) function with the same x value fetch the result from the cache rather than recomputing it, significantly saving time especially for ranges with repeated power sequences.

Sort and Retrieve `kth` Element

The Solution class has a method getKth(lo, hi, k) which leverages the f(x) function to accomplish the task. Here is the step by step approach:

Generate a list of integers from lo to hi, inclusive. This list represents all the candidates for sorting.
Use the sorted function to sort this range, passing f as the key argument. By doing this, Python will call f(x) on each element of the range and sort the numbers according to the values returned by f(x). In case of a tie in power values, the sorted function defaults to sorting by the numbers themselves, maintaining them in ascending order.

The sorted function has a time complexity of O(n log n), where n represents the length of the list being sorted. Given that the cache is in place, each power computation (beyond the first instance) takes O(1) time thanks to the memoization.
Once the list is sorted, we are interested in the kth value of this sorted sequence. We simply index into the sorted list with k - 1 (to account for 0-based indexing) and return this value.
The final returned value is the kth smallest element by power value, and by numerical order in case of identical powers.

The algorithm's main time complexity is driven by the sorting step which is O(n log n). The space complexity includes O(n) for the list of integers and the additional space required by the cache, which at most will be O(n) for a range of different numbers requiring distinct power calculations.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach. Suppose we are given the input lo = 6, hi = 10, and k = 3. We aim to find the 3rd smallest integer by power value in the range [6, 10]. We will calculate the power for each integer within the range and sort them accordingly.

First, we need to compute the power for each integer:

The power of 6: 6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1 (total 8 steps).
The power of 7: 7 → 22 → 11 → 34 → 17 → 52 → 26 → 13 → 40 → 20 → 10 → 5 → ... (we have already calculated this from 5: 5 steps). Hence, the total is 12 + 5 = 17 steps.
The power of 8: 8 → 4 → 2 → 1 (total 3 steps).
The power of 9: 9 → 28 → 14 → 7 → ... (we have already calculated this from 7: 17 steps). So the total is 3 + 17 = 20 steps.
The power of 10: 10 → 5 → ... (we have already calculated from 5: 5 steps). Hence, the total is 1 + 5 = 6 steps.

Next, we sort these integers by their power values:

Power values in ascending order: 3 (8), 6 (8), 10 (6), 7 (17), 9 (20).
Since 3 and 6 have the same power value (8), they will be sub-sorted by their natural values.

So the sorted list by power and natural values is: 6, 8, 10, 7, 9. We want the 3rd smallest integer by power value, which is the integer at index 2 in the sorted list (keeping in mind 0-based indexing). Therefore, the answer is 10.

We achieved this using the following steps:

Create the helper function f(x) with the @cache decorator to calculate power values and make subsequent calculations faster by using cached results.
Generate the list of integers from lo to hi inclusive, which in our case is [6, 7, 8, 9, 10].
Use Python's sorted function with f as the key argument to sort the integers by their power values and by their natural values if there are ties.
Index into the sorted array with k - 1, which is 3 - 1 = 2 in our example, to get the 3rd smallest item according to the defined criteria. Our final result is the integer 10.

This walkthrough exemplifies how the given solution approach effectively finds the kth smallest integer by its "power" value within a given range.

Solution Implementation

1from functools import lru_cache
2
3# Decorator to cache the results of the function to avoid recalculation
4@lru_cache(maxsize=None)
5def compute_steps(x: int) -> int:
6    # Initialize the number of steps taken to reach 1
7    steps = 0
8    # Loop until x becomes 1
9    while x != 1:
10        # If x is even, halve it
11        if x % 2 == 0:
12            x //= 2
13        # If x is odd, apply 3x + 1
14        else:
15            x = 3 * x + 1
16        # Increment the step count for each iteration
17        steps += 1
18    # Return the total number of steps taken
19    return steps
20
21class Solution:
22    def getKth(self, lo: int, hi: int, k: int) -> int:
23        # Sort the range [lo, hi] by the number of steps to reach 1
24        # for each number, as determined by the compute_steps function
25        # Then, retrieve the k-th element in this sorted list.
26        return sorted(range(lo, hi + 1), key=compute_steps)[k - 1]
27

1class Solution {
2  
3    // Method to get the k-th integer in the range [lo, hi] after sorting by a custom function
4    public int getKth(int lo, int hi, int k) {
5        // Create an array of Integers to store the range [lo, hi]
6        Integer[] numbers = new Integer[hi - lo + 1];
7      
8        // Fill the array with numbers from lo to hi
9        for (int i = lo; i <= hi; ++i) {
10            numbers[i - lo] = i;
11        }
12      
13        // Sort the array using a custom comparator based on the transformation count
14        Arrays.sort(numbers, (a, b) -> {
15            int transformCountA = computeTransformCount(a);
16            int transformCountB = computeTransformCount(b);
17            if (transformCountA == transformCountB) {
18                return a - b; // If counts are equal, sort by natural order
19            } else {
20                return transformCountA - transformCountB; // Otherwise, sort by the count
21            }
22        });
23      
24        // Return the k-th element after sorting
25        return numbers[k - 1];
26    }
27
28    // Helper method computing the number of steps to reach 1 based on the Collatz conjecture
29    private int computeTransformCount(int x) {
30        int count = 0; // Initialize step count
31      
32        // While x is not 1, apply the Collatz function and increase the count
33        while (x != 1) {
34            if (x % 2 == 0) {
35                x /= 2; // If x is even, divide it by 2
36            } else {
37                x = x * 3 + 1; // If x is odd, multiply by 3 and add 1
38            }
39            count++;
40        }
41      
42        return count;
43    }
44}
45

1class Solution {
2public:
3    // This function computes the k-th integer in the range [lo, hi] such that 
4    // an integer x's power value is defined as the minimum number of steps 
5    // to reach 1 when we start from x and iteratively apply the following operations:
6    // If x is even, replace it with x / 2.
7    // If x is odd, replace it with 3 * x + 1.
8    int getKth(int lo, int hi, int k) {
9        // Lambda function to calculate the power value of a number
10        auto calculatePower = [](int x) {
11            int power = 0;
12            while (x != 1) {
13                x = (x % 2 == 0) ? x / 2 : 3 * x + 1;
14                ++power;
15            }
16            return power;
17        };
18      
19        // Vector to store the range of numbers from lo to hi
20        vector<int> numbers;
21        for (int i = lo; i <= hi; ++i) {
22            numbers.push_back(i);
23        }
24      
25        // Sort the range of numbers based on their power value
26        // If two numbers have the same power value, the smaller number comes first
27        sort(numbers.begin(), numbers.end(), [&](int x, int y) {
28            int powerX = calculatePower(x);
29            int powerY = calculatePower(y);
30            return (powerX != powerY) ? powerX < powerY : x < y;
31        });
32      
33        // Return the k-th element in the sorted list
34        return numbers[k - 1];
35    }
36};
37

1// Define a helper function to calculate the power value for a given integer.
2// The power value is the number of steps to transform the integer to 1 using the following process:
3// If x is even, divide it by 2.
4// If x is odd, multiply by 3 and add 1.   
5function calculatePowerValue(x: number): number {
6    let steps = 0;
7    while (x !== 1) {
8        steps++;
9        if (x % 2 === 0) {
10            x >>= 1; // If x is even, right shift to divide by 2.
11        } else {
12            x = x * 3 + 1; // If x is odd, multiply by 3 and then add 1.
13        }
14    }
15    return steps;
16}
17
18// Function to get the k-th integer in the range [lo, hi] after sorting by their power value.
19// If two integers have the same power value, then sort them by numerical value.
20function getKth(lo: number, hi: number, k: number): number {
21    // Create an array of all integers from lo to hi, inclusive.
22    const nums: number[] = new Array(hi - lo + 1).fill(0).map((_, index) => lo + index);
23
24    // Sort the array based on the power value calculated via the helper function.
25    // If two integers have the same power value, they will be sorted numerically instead.
26    nums.sort((a, b) => {
27        const powerA = calculatePowerValue(a);
28        const powerB = calculatePowerValue(b);
29        if (powerA === powerB) {
30            return a - b; // Sort by numerical value if power values are equal.
31        }
32        return powerA - powerB; // Sort by power value.
33    });
34
35    // Return the k-th element in the sorted array, considering array indices start at 0.
36    return nums[k - 1];
37}
38

Time and Space Complexity

The time complexity and space complexity of the method getKth in the Solution class can be understood in parts.

Firstly, the function f is decorated with @cache, which uses memoization to store the results of inputs to avoid redundant calculations. The complexity of function f without memoization is tough to quantify precisely, as it requires understanding the behavior of the Collatz sequence, which is a longstanding unsolved problem in mathematics. Nevertheless, each call to the uncached function f performs a series of operations proportional to the length of the sequence required to reach 1, starting from x. During this sequence, the "halving" operation (x //= 2) may occur O(log x) times, while the "tripling plus one" operation (x = 3 * x + 1) is more unpredictable. Despite this, for our complexity analysis, we can assume a worst-case scenario where these operations would result in a complexity of O(log x) on average per function call due to memoization, as previously computed results would be reused.

The method getKth sorts the range [lo, hi], inclusive. Let n = hi - lo + 1 be the number of elements in this range. The sorted function applies the f function as a key, and because of the caching of f, each unique call is O(log x). However, because we are sorting n elements, the sorting operation has a time complexity of O(n log n). Since each element requires calling function f, and assuming f costs O(log hi) at most given its upper bound, the overall time complexity is O(n log n * log hi).

The space complexity primarily comes from two sources: the memoization cache and the sorted list. The cache's size is unbounded and depends on the range of numbers and the length of the Collatz sequences encountered—it can potentially reach O(hi) in space due to the range of unique values passed to f. However, if many values share similar Collatz paths, which is quite possible, the actual memory usage may be significantly less. The sorted list has a space complexity of O(n). Thus, the overall space complexity may be approximated as O(hi) given the potentially large cache size.

In summary:

Time Complexity: O(n log n * log hi)
Space Complexity: O(hi)

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Which two pointer techniques do you use to check if a string is a palindrome?

Fast-slow pointers

Two pointers moving in opposite direction

Sliding window

Prefix sum

I don’t know