1387. Sort Integers by The Power Value

Problem

The power of an integer x is defined as the number of steps needed to transform x into 1 using the following steps:

if x is even then x = x / 2
if x is odd then x = 3 * x + 1

For 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 kᵗʰ 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.

https://leetcode.cn/problems/sort-integers-by-the-power-value/

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

Test Cases

1 2	class Solution: def getKth(self, lo: int, hi: int, k: int) -> int:

solution_test.py

import pytest

from solution import Solution


@pytest.mark.parametrize('lo, hi, k, expected', [
    (12, 15, 2, 13),
    (7, 11, 4, 7),
])
@pytest.mark.parametrize('sol', [Solution()])
def test_solution(sol, lo, hi, k, expected):
    assert sol.getKth(lo, hi, k) == expected

Thoughts

关键是计算出 [lo, hi] 之间每个数字的 power 值。直接用模拟计算，把所有见过的结果都缓存起来避免重复计算。

PS: 在 LeetCode 里，把带缓存的 power 函数放在 Solution 外部，速度更快（相当于在每个 test case 之间都保留缓存）。

Code

solution.py

from functools import cache


@cache
def power(x: int) -> int:
    if x == 1:
        return 1
    elif x & 1:
        return 1 + power(3 * x + 1)
    else:
        return 1 + power(x >> 1)


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

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。