AlgorithmsDynamic ProgrammingGraphsLeetCode SolutionsMedium DifficultyPythonRecursionRecursive DFS

# [LeetCode 1387] Sort Integers by The Power Value

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.
```

Example 2:

```Input: lo = 1, hi = 1, k = 1
Output: 1
```

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.
```

Example 4:

```Input: lo = 10, hi = 20, k = 5
Output: 13
```

Example 5:

```Input: lo = 1, hi = 1000, k = 777
Output: 570
```

Constraints:

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

## RECURSIVE DFS

```import functools

class Solution:
@staticmethod
@functools.lru_cache(maxsize=None)
def transform_steps(n):
if n == 1:
return 0
return 1 + Solution.transform_steps(int(n/2) if n%2 == 0 else int(3*n + 1))
def getKth(self, lo: int, hi: int, k: int) -> int:
return list(sorted(range(lo, hi+1), key=Solution.transform_steps))[k-1]```
```num_to_power = {}
def power(n: int) -> int:
if n == 1:
return 0
elif n in num_to_power:
return num_to_power[n]
else:
if ((n % 2) == 1):
next_number = ((3 * n) + 1)
else:
next_number = (n / 2)
result = power(next_number) + 1
num_to_power[n] = result
return result
class Solution:
def getKth(self, lo: int, hi: int, k: int) -> int:
nums = list(range(lo, hi + 1))
nums.sort(key=power)
# print(nums)
return nums[k - 1]```
```import functools

@functools.lru_cache(maxsize=None)
def find_length(x):
if x == 1:
return 0
elif x & 1:
return 1 + find_length(3 * x + 1)
else:
return 1 + find_length(x >> 1)

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

values = []
for x in range(lo, hi+1):
values.append((find_length(x), x))

values.sort(key=lambda x: x[0])

return values[k-1][1]
```
```class Solution:
pow_cache = {}

def getPow(self,x):

if x in self.pow_cache:
return self.pow_cache[x]

if x == 1:
my_pow = 1
else:
if (x % 2) == 0:
# even
my_pow = self.getPow(x/2)+1
else:
# odd
my_pow = self.getPow(3*x+1)+1

self.pow_cache[x] = my_pow
return my_pow

def getKth(self, lo: int, hi: int, k: int) -> int:
pow_list = []
for i in range(lo,hi+1):
pow_list.append((self.getPow(i),i))

sorted_list = sorted(pow_list)
return sorted_list[k-1][1]```
```class Solution:

p_v=collections.defaultdict()

def powerValue(self, x):

if x in self.p_v:
return self.p_v[x]
if x == 1:
self.p_v[1] = 1
return 1

if x%2 == 0:
self.p_v[x] = 1+self.powerValue(x//2)
else:
self.p_v[x] = 1+self.powerValue(3*x+1)
return self.p_v[x]

def getKth(self, lo: int, hi: int, k: int) -> int:
# build dictionary of power_v
for i in range(lo, hi+1):
self.powerValue(i)

mapping=[]
for i in range(lo, hi+1):
mapping.append((self.p_v[i],i))

return sorted(mapping, key=lambda element: (element[0], element[1]))[k-1][1]```
```d = {}
class Solution:
def power(self,n):
if n == 1:
return 0

if n == 2:
return 1

if n in d:
return d[n]

if n%2 == 0:
d[n] = 1+self.power(n//2)
return d[n]

else:
d[n] = 1+self.power(3*n+1)
return d[n]

def getKth(self, lo: int, hi: int, k: int) -> int:
ans = []
inp = []
for i in range(lo,hi+1):
d[i] = self.power(i)
inp.append(i)
ans.append(d[i])

ans,inp = zip(*sorted(zip(ans,inp)))
# print(inp)
# print(ans)
return inp[k-1]```
```class Solution:
def getKth(self, lo: int, hi: int, k: int) -> int:
from functools import lru_cache

@lru_cache(maxsize=None)
def power(n):
if n == 1:
return 0
if n % 2 == 0:
return 1+power(n//2)
else:
return 1+power(3*n+1)

nums = [n for n in range(lo, hi+1)]
nums.sort(key=power)
return nums[k-1]```
```class Solution:
def getKth(self, lo: int, hi: int, k: int) -> int:
power = {1:0}

def find(x):
if x in power:
return power[x]
if x%2:
power[x] = 2 + find((3*x+1)//2)
else:
power[x] = 1 + find(x//2)
return power[x]

nums = [i for i in range(lo,hi+1)]
nums = sorted(nums, key = lambda x: find(x))
return nums[k-1]```

## sorting and memoization

Time: `O(sort)`
Space: `O(sort + memoization)`

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

@lru_cache(None)
def power(x):
if x == 1:
return 0
if x % 2 == 0:
return 1 + power(x // 2)
return 1 + power(3 * x + 1)

return sorted(range(lo, hi+1), key=power)[k-1]```
Previous Post

Next article