C++ में पावर वैल्यू के आधार पर पूर्णांकों को छाँटें

जैसा कि हम जानते हैं कि एक पूर्णांक x की शक्ति को निम्नलिखित चरणों का उपयोग करके x को 1 में बदलने के लिए आवश्यक चरणों की संख्या के रूप में परिभाषित किया गया है -

• यदि x सम है तो x =x/2

• यदि x विषम है तो x =3 * x + 1

तो उदाहरण के लिए, x =3 की शक्ति 7 है क्योंकि 3 बनने के लिए 3 चरणों का उपयोग करता है (3 → 10 → 5 → 16 → 8 → 4 → 2 → 1)। इसलिए यदि हमारे पास कुछ पूर्णांक lo, hi और k हैं। हमें अंतराल [lo, hi] के सभी पूर्णांकों को घातांक के अनुसार आरोही क्रम में क्रमबद्ध करना है। अब यदि दो या दो से अधिक पूर्णांकों का घातांक समान है, तो उन्हें आरोही क्रम से क्रमबद्ध करें। हमें k-वें पूर्णांक को श्रेणी [lo, hi] में घात मान के अनुसार क्रमबद्ध करना होगा।

उदाहरण के लिए, यदि इनपुट lo =12, hi =15 और k =2 जैसा है, तो आउटपुट 13 होगा। ऐसा इसलिए है क्योंकि 12 की शक्ति 9 है, 13 की शक्ति 9 है, 14 के लिए यह 17 है, और 15 के लिए यह 17 भी है, इसलिए क्रमबद्ध क्रम [12,13,14,15] है और k =2 के रूप में, तो तत्व 13 है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• GetTurn विधि को परिभाषित करें, यह n को इनपुट के रूप में लेगा

• रिट:=0

• जबकि n 1 नहीं है

  • यदि n विषम है, तो n :=n * 3 + 1, अन्यथा n :=n/2

  • रिट को 1 से बढ़ाएं

• मुख्य विधि से

• क्योंकि मैं लो से हाय तक की सीमा में हूं

  • एक जोड़ी बनाएं (getTurn(i), i)

  • रिट में अस्थायी डालें

• जोड़े को शक्ति के आधार पर क्रमबद्ध करें, अन्यथा आरोही क्रम में

• जोड़ी का दूसरा मान लौटाएं ret[k - 1]

उदाहरण (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