The power of an integer x is defined as the number of steps needed to transform x into 1 using the following steps:
x is even then x = x / 2x is odd then x = 3 * x + 1For example, the power of x = 3 is 7 because 3 needs 7 steps to become 1 (3 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1).
Given three integers lo, hi and k. The task is to sort all integers in the interval [lo, hi] by the power value in ascending order, if two or more integers have the same power value sort them by ascending order.
Return the kth integer in the range [lo, hi] sorted by the power value.
Notice that for any integer x (lo <= x <= hi) it is guaranteed that x will transform into 1 using these steps and that the power of x is will fit in a 32-bit signed integer.
Example 1:
Input: lo = 12, hi = 15, k = 2 Output: 13 Explanation: The power of 12 is 9 (12 --> 6 --> 3 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1) The power of 13 is 9 The power of 14 is 17 The power of 15 is 17 The interval sorted by the power value [12,13,14,15]. For k = 2 answer is the second element which is 13. Notice that 12 and 13 have the same power value and we sorted them in ascending order. Same for 14 and 15.
Example 2:
Input: lo = 7, hi = 11, k = 4 Output: 7 Explanation: The power array corresponding to the interval [7, 8, 9, 10, 11] is [16, 3, 19, 6, 14]. The interval sorted by power is [8, 10, 11, 7, 9]. The fourth number in the sorted array is 7.
Constraints:
1 <= lo <= hi <= 10001 <= k <= hi - lo + 1Problem Overview: Given integers lo, hi, and k, compute the power value for every number in the range. The power value is the number of steps required to reduce a number to 1 using the Collatz rules: if even divide by 2, if odd multiply by 3 and add 1. After computing power values, sort the integers by power (and by value if tied) and return the k-th element.
Approach 1: Direct Power Calculation and Sorting (Time: O(n log n * k), Space: O(n))
Iterate through every integer from lo to hi and compute its power value by repeatedly applying the Collatz transformation until reaching 1. Store pairs like (power, value) in a list. Once all values are processed, sort the list by power first and by integer value as a tiebreaker using standard sorting. Finally return the value at index k - 1. This approach is straightforward and works well for the given constraints, but many power calculations repeat the same intermediate numbers.
Approach 2: Memoization for Power Calculation (Time: O(n log n), Space: O(n))
The Collatz sequence frequently revisits numbers whose power values were already computed. Use memoization to cache results in a hash map where memo[x] stores the power of x. When computing the power for a new number, check the cache before continuing the sequence. If an intermediate value already exists in the map, reuse it and stop the traversal early. This reduces repeated work significantly. After computing powers for all numbers, sort the (power, value) pairs using the same rule as before. The memo table effectively turns repeated sequence work into constant-time lookups and behaves like a lightweight dynamic programming cache.
Recommended for interviews: The memoization approach is what most interviewers expect. The direct calculation demonstrates understanding of the Collatz process and sorting mechanics, but caching intermediate results shows awareness of repeated subproblems and optimization using dynamic programming techniques.
This approach involves calculating the power value of each integer in the range [lo, hi] by simulating the steps to transform the number into 1. Once the power values are calculated, the list of integers is sorted by their power value (breaking ties using their magnitude). Finally, the k-th integer is retrieved.
The function calculate_power(x) computes the power value of x by iterating until x becomes 1. For each integer in the range [lo, hi], the power value is calculated and stored in a list. This list is then sorted by power value and magnitude. The k-th integer is returned from this sorted list.
Python
JavaScript
C#
Time Complexity: O(n * m), where n is the number of integers between lo and hi, and m is the average number of steps to reduce an integer to 1.
Space Complexity: O(n) for storing the power values.
This approach improves on the first by using memoization to store previously calculated power values, which reduces redundant calculations and enhances performance when calculating power for subsequent numbers.
The calculatePower method utilizes memoization by storing calculated power values in a hashmap to avoid recalculating them. The result is a more efficient computation for subsequent numbers. Power values for the range [lo, hi] are computed, stored, and sorted as before, allowing retrieval of the k-th element.
Time Complexity: O(n log n) for sorting, as calculations are faster with memoization.
Space Complexity: O(n) for the power cache and list storage.
First, we define a function f(x), which represents the number of steps required to transform the number x into 1, i.e., the power value of the number x.
Then, we sort all the numbers in the interval [lo, hi] in ascending order based on their power values. If the power values are the same, we sort them in ascending order based on the numbers themselves.
Finally, we return the k-th number in the sorted list.
The time complexity is O(n times log n times M), and the space complexity is O(n). Here, n is the number of numbers in the interval [lo, hi], and M is the maximum value of f(x), which is at most 178 in this problem.
| Approach | Complexity |
|---|---|
| Direct Power Calculation and Sorting | Time Complexity: O(n * m), where n is the number of integers between lo and hi, and m is the average number of steps to reduce an integer to 1. |
| Memoization for Power Calculation | Time Complexity: O(n log n) for sorting, as calculations are faster with memoization. |
| Custom Sorting | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Power Calculation and Sorting | O(n log n * k) | O(n) | Good baseline solution when implementing Collatz steps directly without optimization. |
| Memoization for Power Calculation | O(n log n) | O(n) | Best choice when many sequences share intermediate values; avoids recomputation. |
17. Sort Integers by The Power Value | Dynamic Programming Series | LeetCode Medium 1387 • AceCoder Academy • 2,964 views views
Watch 8 more video solutions →Practice Sort Integers by The Power Value with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor