Lũy thừa của một số nguyên x được định nghĩa là số bước cần để biến x thành 1 bằng các quy tắc: nếu x chẵn thì x = x/2; nếu x lẻ thì x = 3*x + 1. Ví dụ: lũy thừa của 3 là 7 vì 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1 (7 bước).
Cho lo, hi và k. Sắp xếp tất cả số nguyên trong khoảng [lo, hi] theo giá trị lũy thừa tăng dần. Nếu cùng lũy thừa, sắp xếp theo giá trị tăng dần. Tìm số nguyên thứ k trong dãy đã sắp xếp.
Ví dụ: lo = 12, hi = 15, k = 2 → 13. Lũy thừa: 12→9, 13→9, 14→17, 15→17. Dãy sắp xếp: [12,13,14,15], phần tử thứ 2 là 13.
Để giải quyết, chúng ta làm theo các bước:
Định nghĩa getTurn(n): ret = 0; khi n != 1: nếu n lẻ thì n = 3*n+1 else n = n/2; ret++; trả về ret.
Từ phương thức chính: với i từ lo đến hi: tạo cặp (getTurn(i), i), thêm vào mảng ret.
Sắp xếp mảng theo lũy thừa, nếu bằng nhau thì theo giá trị.
Trả về giá trị thứ hai của cặp ret[k-1].
Ví dụ (C++)
Hãy xem triển khai sau để 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;
}
};
int main(){
Solution ob;
cout << (ob.getKth(12, 15, 2));
}
Đầu vào
12 15 2
Đầu ra
13