Sort Integers by The Power Value
The power of an integer x is defined as the number of steps needed to transform x into 1 using the following steps:
- If
xis even, thenx = x / 2. - If
xis odd, thenx = 3 * x + 1.
Given three integers lo, hi, and k, sort all integers in the interval [lo, hi] by their power value in ascending order. If two or more integers have the same power value, sort them by ascending order.
Return the k^th integer in the range [lo, hi] after sorting by power value.
For any integer x where lo <= x <= hi, it is guaranteed that x will transform into 1 using these steps and that the power of x will fit in a 32-bit signed integer.
Example 1
Input
lo = 12, hi = 15, k = 2Output
13The interval sorted by power value is [12, 13, 14, 15], so the second element is 13.
Example 2
Input
lo = 7, hi = 11, k = 4Output
7The interval sorted by power is [8, 10, 11, 7, 9], so the fourth number is 7.
Constraints
- 1 <= lo <= hi <= 1000
- 1 <= k <= hi - lo + 1