Sắp xếp số nguyên theo giá trị lũy thừa trong C ++

Như chúng ta biết rằng lũy ​​thừa của một số nguyên x được xác định là số bước cần thiết để biến x thành 1 bằng cách sử dụng các bước sau -

• nếu x chẵn thì x =x / 2

• nếu x lẻ thì x =3 * x + 1

Vì vậy, ví dụ, lũy thừa của x =3 là 7 vì 3 sử dụng 7 bước để trở thành 1 (3 → 10 → 5 → 16 → 8 → 4 → 2 → 1). Vì vậy, nếu chúng ta có một số số nguyên lo, hi và k. Chúng ta phải sắp xếp tất cả các số nguyên trong khoảng [lo, hi] theo giá trị lũy thừa theo thứ tự tăng dần. Bây giờ nếu hai hoặc nhiều số nguyên có cùng giá trị lũy thừa, hãy sắp xếp chúng theo thứ tự tăng dần. Chúng ta phải tìm số nguyên thứ k trong phạm vi [lo, hi] được sắp xếp theo giá trị lũy thừa.

Ví dụ:nếu đầu vào là lo =12, hi =15 và k =2, thì đầu ra sẽ là 13. Điều này là do lũy thừa của 12 là 9, lũy thừa của 13 là 9, đối với 14, đây là 17, và đối với 15 thì cũng là 17, do đó, dãy được sắp xếp là [12,13,14,15] và là k =2, thì phần tử là 13.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định phương thức getTurn, phương thức này sẽ lấy n làm đầu vào

• ret:=0

• trong khi n không phải là 1

  • nếu n lẻ thì n:=n * 3 + 1, ngược lại n:=n / 2

  • tăng ret lên 1

• Từ phương thức chính

• cho tôi trong phạm vi lo đến chào

  • tạo một cặp (getTurn (i), i)

  • chèn tạm thời vào ret

• sắp xếp các cặp dựa trên sức mạnh, nếu không thì theo thứ tự tăng dần

• trả về giá trị thứ hai của cặp ret [k - 1]

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn -

#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));
}

Đầu vào

12
15
2

Đầu ra

13