Sort Integers by The Power Value ใน C++ : เรียงลำดับตาม Power Value (Collatz Steps)

• x even -> x = x / 2
• x odd -> x = 3*x + 1

ให้ Range [lo, hi] และ k เรียงจำนวนใน Range ตาม **Power Value 昇序 (น้อยไปมาก)** ถ้า Power เท่ากัน เรียงตาม **ค่าตัวเลข 昇序** หา **ตัวเลขลำดับที่ k**

ตัวอย่าง

lo=12, hi=15, k=2

• 12: 9 steps
• 13: 9 steps
• 14: 17 steps
• 15: 17 steps

Sorted: [12, 13, 14, 15] (12,13 Power=9; 14,15 Power=17) -> k=2 คือ 13

แนวทาง: Compute Power + Sort Pairs

1. Function getTurn(n) คำนวณ Power Steps (Loop จน n==1)
2. สร้าง Vector of Pairs {power, value} สำหรับทุก i ใน [lo, hi]
3. Sort ด้วย Comparator: power asc, then value asc
4. Return ret[k-1].second

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    static bool cmp(const pair<int, int>& a, const pair<int, int>& b) {
        return a.first == b.first ? a.second < b.second : a.first < b.first;
    }

    int getTurn(int n) {
        int steps = 0;
        while (n != 1) {
            if (n & 1) n = n * 3 + 1;
            else n >>= 1;
            steps++;
        }
        return steps;
    }

    int getKth(int lo, int hi, int k) {
        vector<pair<int, int>> vec;
        for (int i = lo; i <= hi; i++) {
            vec.push_back({getTurn(i), i});
        }
        sort(vec.begin(), vec.end(), cmp);
        return vec[k - 1].second;
    }
};

Input / Output

Input:  12 15 2
Output: 13

ความซับซ้อน (Complexity)

• Time: O((hi-lo) * log(hi) + (hi-lo) log(hi-lo)) — Compute Power (log steps) + Sort
• Space: O(hi-lo)

Optimization: Memoization

Power Values ซ้ำกันเยอะ (เช่น 10, 5, 16, 8, 4, 2, 1) ควร Cache getTurn ผลลัพธ์ไว้ (Map/Array) จะเร็วขึ้นมากสำหรับ Range ใหญ่ครับ