#1387

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Sort Integers by The Power Value

Sort integers in a range based on their power value using dynamic programming and memoization, handling ties with ascending order.

dynamic programming memoization sorting

Problem Statement

Given three integers lo, hi, and k, compute the power of every integer x in the interval [lo, hi], where the power of x is the number of steps to reach 1 using the following rules: if x is even, divide by 2; if x is odd, multiply by 3 and add 1. Sort all integers by their power value in ascending order; if multiple integers share the same power, sort them in ascending numerical order.

Return the k-th integer in the sorted interval. For example, if lo = 12, hi = 15, and k = 2, the computed powers are [12:9, 13:9, 14:17, 15:17], the sorted interval is [12, 13, 14, 15], and the answer is 13.

Examples

Example 1

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

Output: 13

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

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 <= 1000
1 <= k <= hi - lo + 1

Solution Approach

Use Memoized Dynamic Programming to Compute Powers

Create a memoization table to store the power of each integer encountered. For each x in [lo, hi], recursively compute its power using the state transition rules. Memoization avoids recalculating powers for numbers appearing multiple times in different sequences.

Sort Integers by Computed Power Values

After computing all powers, sort the list of integers using a comparator that first orders by power value and then by the integer itself to handle ties. This ensures the correct order for retrieving the k-th element.

Retrieve the k-th Element Efficiently

Once the sorted list is prepared, directly return the element at index k-1. This step is simple but must be done after accurate computation and sorting to ensure correctness in tie situations.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n log n) for sorting n = hi - lo + 1 integers, plus O(n * log m) for power computation using memoization (where m is the largest intermediate number). Space complexity is O(m) for the memoization table storing intermediate power values.

What Interviewers Usually Probe

Check if memoization reduces repeated calculations of power values.
Expect clarification on sorting ties by ascending integer value.
Notice if the candidate uses a recursive DP vs iterative DP for power computation.

Common Pitfalls or Variants

Common pitfalls

Failing to memoize powers leads to redundant recursion and timeouts.
Sorting integers only by power without handling ties incorrectly orders results.
Not handling k-1 indexing correctly when retrieving the k-th element.

Follow-up variants

Return all integers sorted by power instead of only the k-th element.
Compute power values using iterative DP rather than recursion with memoization.
Extend the range beyond 1000, requiring optimization for larger integers.

FAQ

What does the power value of an integer mean in this problem?

The power value is the number of steps to reduce an integer to 1 using the rules: divide by 2 if even, multiply by 3 and add 1 if odd.

Why is memoization critical for this problem?

Memoization prevents recalculating the power for integers that appear multiple times in sequences, which dramatically improves efficiency.

How are ties handled when multiple integers have the same power value?

Integers with the same power are sorted in ascending numerical order to determine their correct position in the final sequence.

Can the approach be used for ranges larger than 1000?

Yes, but careful memoization and possibly iterative DP are required to handle larger ranges efficiently without timeouts.

How does state transition dynamic programming apply here?

Each integer's power depends on previous states (its next number in the sequence), making it a classic DP problem where memoization stores intermediate results to avoid repeated computation.

terminal

Solution

Solution 1: Custom Sorting

First, we define a function $\textit{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$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

@cache
def f(x: int) -> int:
    ans = 0
    while x != 1:
        if x % 2 == 0:
            x //= 2
        else:
            x = 3 * x + 1
        ans += 1
    return ans


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        return sorted(range(lo, hi + 1), key=f)[k - 1]

Continue Practicing

#1402 reducing dishes #1363 largest multiple of three #1340 jump game v