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?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 <= 1000

• 1 <= k <= hi - lo + 1

之前是日本人提出的一個猜想，所有的數(shù)字如果是偶數(shù)就除以2，如果是奇數(shù)就乘以3+1，最后都會回歸到1的。

1：先寫個函數(shù)，判斷這個數(shù)的power值是多少。

2：然后將lo到hi的數(shù)字放到二維數(shù)組中，第2個元素就是這個數(shù)字的power值；

3：對2維數(shù)組排序。

返回第k-1的數(shù)字即可；

Runtime:?62 ms, faster than?54.26%?of?Java?online submissions for?Sort Integers by The Power Value.

Memory Usage:?41.9 MB, less than?84.75%?of?Java?online submissions for?Sort Integers by The Power Value.