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 lohi 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]

Leave a reply