LeetCode 1387: Sort Integers by The Power Value Solution

Master LeetCode problem 1387 (Sort Integers by The Power Value), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1387. Sort Integers by The Power Value

Medium

Dynamic Programming Memoization Sorting

Problem Explanation

Explanation:

To solve this problem, we will iterate through all integers in the range [lo, hi] and calculate the power value for each integer using the given rules. Then, we will sort the integers based on their power values in ascending order. Finally, we will return the k-th element from the sorted list.

Here's the high-level algorithm:

Create a helper function to calculate the power value for a given integer according to the given rules.
Iterate through all integers in the range [lo, hi].
Calculate the power value for each integer.
Store the integer along with its power value in a list.
Sort the list based on the power values in ascending order.
Return the k-th element from the sorted list.

Time complexity analysis:

Calculating the power value for each integer takes O(log n) steps, where n is the integer value.
We iterate through all integers in the range [lo, hi], so the overall time complexity is O((hi - lo) * log hi).
Sorting the list of integers by power values takes O(n log n) time.
Thus, the total time complexity is dominated by the sorting step, O((hi - lo) * log hi).

Space complexity:

We store the power values along with the integers in a list, which requires O(hi - lo) space for the worst-case scenario where all integers in the range have unique power values.

Solution Code

import java.util.*;

class Solution {
    public int getKth(int lo, int hi, int k) {
        List<int[]> powerValues = new ArrayList<>();
        
        for (int i = lo; i <= hi; i++) {
            powerValues.add(new int[]{i, calculatePower(i)});
        }
        
        Collections.sort(powerValues, (a, b) -> a[1] != b[1] ? Integer.compare(a[1], b[1]) : Integer.compare(a[0], b[0]));
        
        return powerValues.get(k - 1)[0];
    }
    
    private int calculatePower(int num) {
        int steps = 0;
        while (num != 1) {
            if (num % 2 == 0) {
                num /= 2;
            } else {
                num = 3 * num + 1;
            }
            steps++;
        }
        return steps;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1387 (Sort Integers by The Power Value)?

This page provides optimized solutions for LeetCode problem 1387 (Sort Integers by The Power Value) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1387 (Sort Integers by The Power Value)?

The time complexity for LeetCode 1387 (Sort Integers by The Power Value) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1387 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1387 in Java, C++, or Python.

Back to LeetCode Solutions