“This is the 16th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

describe

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-th 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 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.Copy the code

Example 2:

Input: lo = 1, hi = 1, k = 1
Output: 1
Copy the code

Example 3:

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.
Copy the code

Example 4:

Input: lo = 10, hi = 20, k = 5
Output: 13
Copy the code

Example 5:

Input: lo = 1, hi = 1000, k = 777
Output: 570
Copy the code

Note:

1 <= lo <= hi <= 1000
1 <= k <= hi - lo + 1
Copy the code

parsing

The number of operations required to change a number x to 1:

  • If x is even, x/ is equal to 2
  • If x is odd, x is equal to 3 times x plus 1

The ranges [lo, hi] and K are then given and we are asked to sort all integers within the range [lo, hi] in ascending power order, and if two or more integers have the same power, they are sorted in ascending order. Returns the KTH integer in the range of [lo, hi] sorted by power. They guarantee that all certificates can be changed from x to 1 by the above operation.

The simplest way to do this is to write a function getPower that gets the power value of a number. It then arranges all integers in order of power and returns the KTH integer.

answer

class Solution(object): def getKth(self, lo, hi, k): """ :type lo: int :type hi: int :type k: int :rtype: int """ def getPower(n): result = 0 while n! =1: if n%2==0: n = n//2 else: n = n * 3 + 1 result += 1 return result d = [] for i in range(lo,hi+1): d.append([i,getPower(i)]) d = sorted(d, key=lambda x: x[1]) return d[k-1][0]Copy the code

The results

Given in The Python online submission for Sort Integers by The Power Value. Memory Usage: The linked submissions in Python online submissions for Sort Integers by The Power Value.Copy the code

parsing

The above solution from [LO, hi] one by one, there are many numerical power values are repeated, you can use dictionary D to directly record the known power numbers, so that a lot of calculation time can be saved in the subsequent calculation process.

answer

class Solution(object):
    def getKth(self, lo, hi, k):
        """
        :type lo: int
        :type hi: int
        :type k: int
        :rtype: int
        """
        d = {1: 1}
        def getPower(n):
            if n not in d:
                if n % 2 == 0:
                    d[n] = 1 + getPower(n / 2)
                else:
                    d[n] = 1 + getPower(3*n + 1)
            return d[n]
        return sorted((getPower(i), i) for i in range(lo, hi+1))[k-1][1]
            
Copy the code

The results

Given in The Python online submission for Sort Integers by The Power Value. Memory Usage: Given in Python online submissions for Sort Integers by The Power Value.Copy the code

Original link: leetcode.com/problems/so…

Your support is my biggest motivation