Solution For Sort Integers By The Power Value

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.

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

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

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.

python
return sorted_list[k-1][0]

The complete code is given below:

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

Step by Step Implementation For Sort Integers By The Power Value

class Solution {
    public int getKth(int lo, int hi, int k) {
        // edge case
        if (lo == hi && k == 1) {
            return lo;
        }
        
        // initialize an array to store all the power values
        int[] powerValues = new int[hi - lo + 1];
        int index = 0;
        
        // fill in the array with the power values
        for (int i = lo; i <= hi; i++) {
            powerValues[index++] = getPowerValue(i);
        }
        
        // sort the array in ascending order
        Arrays.sort(powerValues);
        
        // return the kth element in the array
        return powerValues[k - 1];
    }
    
    // helper function to get the power value of a number
    public int getPowerValue(int num) {
        int powerValue = 0;
        
        while (num != 1) {
            if (num % 2 == 0) {
                num /= 2;
            } else {
                num = 3 * num + 1;
            }
            powerValue++;
        }
        
        return powerValue;
    }
}

def getKth(lo: int, hi: int, k: int) -> int:
    # Sort the given integers by their power value in ascending order
    # and return the kth element from the sorted list
    
    # Create a list of tuples consisting of the integer and its power value
    int_power = [(i, power(i)) for i in range(lo, hi + 1)]
    
    # Sort the list of tuples by the power value
    int_power.sort(key = lambda x: x[1])
    
    # Return the kth element from the sorted list
    return int_power[k - 1][0]

var getKth = function(lo, hi, k) {
    
    // create an array to store the results
    let results = [];
    
    // create a helper function to calculate the power value
    let powerValue = (num) => {
        let count = 0;
        while (num !== 1) {
            count++;
            if (num % 2 === 0) {
                num = num / 2;
            } else {
                num = 3 * num + 1;
            }
        }
        return count;
    }
    
    // fill the results array with the power values
    for (let i = lo; i <= hi; i++) {
        results.push(powerValue(i));
    }
    
    // sort the results array in ascending order
    results.sort((a, b) => a - b);
    
    // return the kth element in the results array
    return results[k - 1];
};

class Solution {
public:
    int getKth(int lo, int hi, int k) {
        // vector to store all the values and their corresponding powers
        vector> power;
        
        // go through all the numbers from lo to hi
        for(int i=lo;i<=hi;i++) {
            // calculate the power of the number
            int p = powerValue(i);
            // store the number and its power in the vector
            power.push_back(make_pair(i,p));
        }
        
        // sort the vector in ascending order of the power values
        sort(power.begin(),power.end(),compare);
        
        // return the kth element from the vector
        return power[k-1].first;
    }
    
    // function to calculate the power value of a number
    int powerValue(int n) {
        // power value
        int p = 0;
        // while n is not equal to 1
        while(n!=1) {
            // if n is even, divide it by 2
            if(n%2==0)
                n/=2;
            // if n is odd, subtract 1 from it
            else
                n--;
            // increment the power value
            p++;
        }
        return p;
    }
    
    // function to compare two pairs
    static bool compare(pair &a,pair &b) {
        // if power values are equal, compare the numbers
        if(a.second==b.second)
            return a.first
public int GetKth(int lo, int hi, int k) 
{
    // Initialize a list to store the power values of all numbers in the given range
    List powerValues = new List();
    
    // Loop through all numbers in the given range
    for (int i = lo; i <= hi; i++)
    {
        // Calculate the power value of the current number
        int powerValue = CalculatePowerValue(i);
        
        // Add the power value to the list
        powerValues.Add(powerValue);
    }
    
    // Sort the list in ascending order
    powerValues.Sort();
    
    // Return the kth element in the sorted list
    return powerValues[k - 1];
}

// Helper method to calculate the power value of a given number
private int CalculatePowerValue(int num)
{
    // Initialize a counter to keep track of the number of steps required
    // to reach 1 when starting from the given number
    int counter = 0;
    
    // Loop until the number reaches 1
    while (num != 1)
    {
        // If the number is even, divide it by 2
        if (num % 2 == 0)
        {
            num /= 2;
        }
        // Otherwise, multiply it by 3 and add 1
        else
        {
            num = num * 3 + 1;
        }
        
        // Increment the counter
        counter++;
    }
    
    // Return the final counter value
    return counter;
}