Sort Integers by The Power Value solution and explanation

def calculate_power(x):
    steps = 0
    while x != 1:
        if x % 2 == 0:
            x //= 2
        else:
            x = 3 * x + 1
        steps += 1
    return steps


def get_kth(lo, hi, k):
    power_values = [(i, calculate_power(i)) for i in range(lo, hi+1)]
    power_values.sort(key=lambda x: (x[1], x[0]))
    return power_values[k-1][0]

# Example usage:
print(get_kth(12, 15, 2))  # Output: 13
print(get_kth(7, 11, 4))   # Output: 7

function calculatePower(x) {
    let steps = 0;
    while (x !== 1) {
        if (x % 2 === 0) x /= 2;
        else x = 3 * x + 1;
        steps++;
    }
    return steps;
}

function getKth(lo, hi, k) {
    const powerValues = [];
    for (let i = lo; i <= hi; i++) {
        powerValues.push({ number: i, power: calculatePower(i) });
    }
    powerValues.sort((a, b) => a.power === b.power ? a.number - b.number : a.power - b.power);
    return powerValues[k - 1].number;
}

// Example usage:
console.log(getKth(12, 15, 2)); // Output: 13
console.log(getKth(7, 11, 4));  // Output: 7

using System;
using System.Collections.Generic;

public class Solution {
    private static int CalculatePower(int x) {
        int steps = 0;
        while (x != 1) {
            if (x % 2 == 0) x /= 2;
            else x = 3 * x + 1;
            steps++;
        }
        return steps;
    }
    
    public int GetKth(int lo, int hi, int k) {
        List<(int Number, int Power)> powerList = new List<(int, int)>();
        for (int i = lo; i <= hi; i++) {
            int powerValue = CalculatePower(i);
            powerList.Add((i, powerValue));
        }
        powerList.Sort((a, b) => a.Power == b.Power ? a.Number.CompareTo(b.Number) : a.Power.CompareTo(b.Power));
        return powerList[k - 1].Number;
    }
}

// Example usage:
// Solution sol = new Solution();
// Console.WriteLine(sol.GetKth(12, 15, 2)); // Output: 13
// Console.WriteLine(sol.GetKth(7, 11, 4));  // Output: 7

import java.util.*;

class Solution {
    Map<Integer, Integer> powerCache = new HashMap<>();

    private int calculatePower(int x) {
        if (x == 1) return 0;
        if (powerCache.containsKey(x)) return powerCache.get(x);

        int next = (x % 2 == 0) ? x / 2 : 3 * x + 1;
        int power = 1 + calculatePower(next);
        powerCache.put(x, power);

        return power;
    }

    public int getKth(int lo, int hi, int k) {
        List<int[]> powerList = new ArrayList<>();
        for (int i = lo; i <= hi; i++) {
            int powerValue = calculatePower(i);
            powerList.add(new int[]{i, powerValue});
        }
        Collections.sort(powerList, (a, b) -> a[1] == b[1] ? a[0] - b[0] : a[1] - b[1]);
        return powerList.get(k - 1)[0];
    }
}

// Example usage:
// Solution sol = new Solution();
// System.out.println(sol.getKth(12, 15, 2)); // Output: 13
// System.out.println(sol.getKth(7, 11, 4)); // Output: 7

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

std::unordered_map<int, int> powerCache;

int calculatePower(int x) {
    if (x == 1) return 0;
    if (powerCache.count(x)) return powerCache[x];

    int next = (x % 2 == 0) ? x / 2 : 3 * x + 1;
    int power = 1 + calculatePower(next);
    powerCache[x] = power;

    return power;
}

int getKth(int lo, int hi, int k) {
    std::vector<std::pair<int, int>> powerList;
    for (int i = lo; i <= hi; ++i) {
        int powerValue = calculatePower(i);
        powerList.emplace_back(i, powerValue);
    }
    std::sort(powerList.begin(), powerList.end(), [](auto& a, auto& b) {
        return a.second == b.second ? a.first < b.first : a.second < b.second;
    });
    return powerList[k - 1].first;
}

int main() {
    std::cout << getKth(12, 15, 2) << std::endl; // Output: 13
    std::cout << getKth(7, 11, 4) << std::endl;  // Output: 7
    return 0;
}

function getKth(lo: number, hi: number, k: number): number {
    const f = (x: number): number => {
        let ans = 0;
        for (; x !== 1; ++ans) {
            if (x % 2 === 0) {
                x >>= 1;
            } else {
                x = x * 3 + 1;
            }
        }
        return ans;
    };
    const nums = new Array(hi - lo + 1).fill(0).map((_, i) => i + lo);
    nums.sort((a, b) => {
        const fa = f(a),
            fb = f(b);
        return fa === fb ? a - b : fa - fb;
    });
    return nums[k - 1];
}

func getKth(lo int, hi int, k int) int {
	f := func(x int) (ans int) {
		for ; x != 1; ans++ {
			if x%2 == 0 {
				x /= 2
			} else {
				x = 3*x + 1
			}
		}
		return
	}
	nums := make([]int, hi-lo+1)
	for i := range nums {
		nums[i] = lo + i
	}
	sort.Slice(nums, func(i, j int) bool {
		fx, fy := f(nums[i]), f(nums[j])
		if fx != fy {
			return fx < fy
		}
		return nums[i] < nums[j]
	})
	return nums[k-1]
}

impl Solution {
    pub fn get_kth(lo: i32, hi: i32, k: i32) -> i32 {
        let f = |mut x: i32| -> i32 {
            let mut ans = 0;
            while x != 1 {
                if x % 2 == 0 {
                    x /= 2;
                } else {
                    x = 3 * x + 1;
                }
                ans += 1;
            }
            ans
        };

        let mut nums: Vec<i32> = (lo..=hi).collect();
        nums.sort_by(|&x, &y| f(x).cmp(&f(y)));
        nums[(k - 1) as usize]
    }
}