ধরুন আমাদের কাছে 1 থেকে n পর্যন্ত সাজানো পূর্ণসংখ্যার তালিকা আছে। এটি বাম থেকে শুরু করে ডানদিকে শেষ হচ্ছে, আমাদের তালিকার শেষ পর্যন্ত না পৌঁছানো পর্যন্ত আমাদের প্রথম নম্বর এবং পরবর্তী প্রতিটি নম্বর মুছে ফেলতে হবে। আমরা আবার পূর্ববর্তী ধাপটি পুনরাবৃত্তি করব, কিন্তু এইবার ডান থেকে বামে, অবশিষ্ট সংখ্যাগুলি থেকে ডান সর্বাধিক সংখ্যা এবং অন্য প্রতিটি সংখ্যা সরিয়ে ফেলুন। আমরা আবার ধাপগুলি পুনরাবৃত্তি করব, বাম থেকে ডানে এবং ডান থেকে বামে পর্যায়ক্রমে, যতক্ষণ না একটি একক সংখ্যা অবশিষ্ট থাকে। আমাদের শেষ সংখ্যাটি খুঁজে বের করতে হবে যা দৈর্ঘ্য n এর তালিকা দিয়ে শুরু করে।
সুতরাং যদি ইনপুটটি n =9 এর মত হয়, তাহলে ধাপগুলি নিম্নরূপ হবে −
-
1 ,2,3 ,4,5 ,6,7 ,8,9
-
2,4 ,6,8
-
2 ,6
-
৬
সুতরাং উত্তর হবে 6.
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
বাম :=1, মাথা :=1, ধাপ :=1, rem :=n
-
যখন rem> 1
-
বাম যদি শূন্য না হয় বা রেম বিজোড় হয়, তাহলে head :=head + step
-
ধাপ :=ধাপ * 2
-
বাম :=বামের বিপরীত
-
rem :=rem / 2
-
-
রিটার্ন হেড
উদাহরণ (C++)
আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int lastRemaining(int n) {
int head = 1;
int step = 1;
int rem = n;
int left = 1;
while(rem > 1){
if(left || rem % 2 == 1){
head += step;
}
step *= 2;
left = !left;
rem /= 2;
}
return head;
}
};
main(){
Solution ob;
cout << (ob.lastRemaining(9));
} ইনপুট
9
আউটপুট
6
