C++で整数をパワー値の順に並べ替えてk番目の要素を求める方法

整数xの「パワー」とは、次の手順を繰り返してxを1へ変換するまでに必要なステップ数として定義されます。

• xが偶数の場合：x = x / 2
• xが奇数の場合：x = 3 * x + 1

例えば、x = 3のパワーは7です。これは、3が1になるまでに7ステップかかるためです（3 → 10 → 5 → 16 → 8 → 4 → 2 → 1）。なお、この変換手順は「コラッツ予想」として知られる数列に関連しており、任意の正の整数は必ず1に到達すると予想されています。

ここで、整数lo、hi、kが与えられたとします。区間[lo, hi]内のすべての整数をパワー値の昇順にソートし、パワー値が同じ場合は整数そのものの昇順で並べ替えます。そのうえで、ソート後のk番目の整数を求めるのがこの問題です。

具体例

入力がlo = 12、hi = 15、k = 2の場合、出力は13になります。各数値のパワーは以下の通りです。

• 12のパワー：9
• 13のパワー：9
• 14のパワー：17
• 15のパワー：17

したがって、ソート後の順序は[12, 13, 14, 15]となり、k = 2番目の要素は13です。

解法のアプローチ

この問題を解くには、以下の手順に従います。

• 引数nを受け取るgetTurnメソッドを定義します。
• ret := 0 で初期化します。
• nが1になるまでループします。
  • nが奇数ならn := n * 3 + 1、偶数ならn := n / 2とします。
  • retを1ずつ増やします。
• メインメソッドでは、iをloからhiまでループします。
  • (getTurn(i), i)というペアを作成します。
  • 作成したペアをretに挿入します。
• ペアをパワー値の昇順でソートします。パワー値が等しい場合は整数値の昇順で並べます。
• ret[k - 1]の2番目の値（元の整数）を返します。

C++での実装例

理解を深めるために、以下の実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    vector < pair <int, int> > ret;
    static bool cmp(pair <int, int>& a, pair <int, int>& b){
        return a.first == b.first ? a.second < b.second : a.first < b.first;
    }
    int getTurn(int n){
        int ret = 0;
        while(n != 1){
            if(n & 1){
                n = n * 3 + 1;
            }
            else n >>= 1;
            ret ++;
        }
        return ret;
    }
    int getKth(int lo, int hi, int k) {
        for(int i = lo; i <= hi; i++){
            pair <int, int> temp;
            temp.first = getTurn(i);
            temp.second = i;
            ret.push_back(temp);
        }
        sort(ret.begin(), ret.end(), cmp);
        return ret[k - 1].second;
    }
};
main(){
    Solution ob;
    cout << (ob.getKth(12, 15, 2));
}

入力

12
15
2

出力

13