Similar Problems

Similar Problems not available

Sort Integers By The Power Value - Leetcode Solution

Companies:

LeetCode:  Sort Integers By The Power Value Leetcode Solution

Difficulty: Medium

Topics: dynamic-programming sorting  

Problem Statement:

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, divide it by 2.
  • If x is odd, multiply it by 3 and add 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.

Solution:

To solve this problem, we need to calculate the power of each and every number in the range [lo, hi] and sort them based on their power values. Then we can return the k-th integer from the sorted list.

First, let's write a function to calculate the power of an integer.

def power(x):
    p = 0
    while x != 1:
        if x % 2 == 0:
            x //= 2
        else:
            x = x * 3 + 1
        p += 1
    return p

This function takes an integer x and returns its power value using the rules mentioned in the problem. Now, we can loop through the range [lo, hi], calculate the power value of each integer and store it in a list along with the integer itself.

list = []
for x in range(lo, hi+1):
    p = power(x)
    list.append((x, p))

Now, we have a list of tuples where each tuple contains an integer and its power value. We can sort this list based on the power value using the sorted() function in Python.

sorted_list = sorted(list, key=lambda x: (x[1], x[0]))

The lambda function is used to sort the list first by the power value and then by the integer value in ascending order. Finally, we can return the k-th integer from the sorted list.

return sorted_list[k-1][0]

The complete code is given below:

def getKth(lo: int, hi: int, k: int) -> int:
    def power(x):
        p = 0
        while x != 1:
            if x % 2 == 0:
                x //= 2
            else:
                x = x * 3 + 1
            p += 1
        return p
    
    list = []
    for x in range(lo, hi+1):
        p = power(x)
        list.append((x, p))
    
    sorted_list = sorted(list, key=lambda x: (x[1], x[0]))
    
    return sorted_list[k-1][0]

Time Complexity:

The time complexity of this solution is O((hi - lo + 1) * log(hi - lo + 1)) due to sorting. However, since hi and lo are both limited to 10^6, this complexity is acceptable.

Sort Integers By The Power Value Solution Code

1