Sort Integers by The Power Value

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 then x = x / 2
• if x is odd then x = 3 * x + 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.

Example 1:

Input: lo = 12, hi = 15, k = 2
Output: 13

Approach

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class SortIntegersByPowerValue {
    public static void main(String[] args) {
        int lo = 12, hi = 15, k = 2;
        System.out.println(getKth(lo, hi, k));
    }

    static int getKth(int lo, int hi, int k) {
        List<int[]> v = new ArrayList<int[]>();
        for (int i = lo; i <= hi; i++) {
            int j = i;
            int p = 0;
            while (j != 1) {
                if (j % 2 == 0)
                    j = j / 2;
                else
                    j = j * 3 + 1;
                p++;
            }
            v.add(new int[] { i, p });
        }
        Collections.sort(v, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[1] == o2[1])
                    return o1[0] - o2[0];
                return o1[1] - o2[1];
            }
        });
        return v.get(k - 1)[0];
    }

}

C++

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

//comparator used for sorting
static bool cmp(pair<int, int> a, pair<int, int> b)
{
    if (a.second == b.second)
        return a.first < b.first;
    return a.second < b.second;
}
int getKth(int lo, int hi, int k)
{
    vector<pair<int, int>> v;
    for (int i = lo; i <= hi; i++)
    {
        int j = i;
        int p = 0;
        while (j != 1)
        {
            if (j % 2 == 0)
                j = j / 2;
            else
                j = j * 3 + 1;
            p++;
        }
        v.push_back({i, p});
    }
    sort(v.begin(), v.end(), cmp);
    return v[k - 1].first;
}

int main()
{
    int lo = 12, hi = 15, k = 2;
    cout << getKth(lo, hi, k);
    return 0;
}