আমরা জানি একটি ইন্টিজার x-এর পাওয়ার বলতে নিচের ধাপগুলো ব্যবহার করে x কে ১-এ রূপান্তর করার জন্য কত স্টেপ লাগে সেটি বোঝায় −
যদি x সম হয় তবে x = x / 2
যদি x বিজোড় হয় তবে x = 3 * x + 1
উদাহরণস্বরূপ, x = 3-এর পাওয়ার ৭ কারণ ৩ ৭ স্টেপে ১ হয় (3 → 10 → 5 → 16 → 8 → 4 → 2 → 1)। যদি আমাদের কিছু ইন্টিজার lo, hi এবং k থাকে। আমাদের [lo, hi] ইন্টারভালের সকল ইন্টিজারকে পাওয়ার ভ্যালু অনুযায়ী অ্যাসেন্ডিং অর্ডারে সোর্ট করতে হবে। যদি দুটি বা অধিক ইন্টিজারের পাওয়ার ভ্যালু একই হয়, তবে সেগুলো অ্যাসেন্ডিং অর্ডারে সোর্ট করুন। [lo, hi] রেঞ্জে পাওয়ার ভ্যালু দিয়ে সোর্ট করা k-তম ইন্টিজার বের করতে হবে।
উদাহরণস্বরূপ, lo = 12, hi = 15, k = 2 হলে আউটপুট হবে ১৩। কারণ ১২-এর পাওয়ার ৯, ১৩-এর পাওয়ার ৯, ১৪-এর ১৭, ১৫-এর ১৭। সোর্টেড সিকোয়েন্স [12,13,14,15] এবং k = 2 হলে এলিমেন্ট ১৩।
সমাধানের ধাপগুলো:
getTurn মেথড ডিফাইন করুন, যা n ইনপুট নেবে
ret := 0
যখন n ১ নয়
যদি n বিজোড় হয়, তবে n := n * 3 + 1, অন্যথায় n := n / 2
ret ১ বাড়ান
মেইন মেথড থেকে
i = lo থেকে hi পর্যন্ত লুপ চালান
পেয়ার (getTurn(i), i) বানান
ret-এ পশ করুন
পেয়ারগুলো পাওয়ার অনুযায়ী সোর্ট করুন, অন্যথায় অ্যাসেন্ডিং অর্ডারে
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
