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.firstpublic 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
}

// 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;
}```
Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]