#1387
Sort Integers by The Power Value
pupil · 545 · lc medium +28 · verified · 71.6% accepted · 1,511 likes · top 81%
Description
Define the power of an integer x as the number of steps in its Collatz sequence to reach 1: if x is even apply x = x / 2; if odd apply x = 3 * x + 1. For example, the power of 3 is 7 because 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1.
Given integers lo, hi, and k, sort all integers in [lo, hi] by power ascending (ties broken by value ascending), and return the kth element (1-indexed). Every value is guaranteed to reach 1 and its power fits in a 32-bit 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.
Code
1
2
3