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