C++-এ এলিমিনেশন গেম

১ থেকে n পর্যন্ত সর্টেড পূর্ণসংখ্যার একটি লিস্ট দেওয়া আছে। বাম থেকে ডানে যেতে প্রথম নম্বর এবং তারপর প্রতিটি অল্টারনেট নম্বর মুছে ফেলুন যতক্ষণ না লিস্টের শেষে পৌঁছান। আবার ডান থেকে বামে যেতে ডানপাশের নম্বর এবং তারপর প্রতিটি অল্টারনেট নম্বর মুছে ফেলুন। বাম-ডান এবং ডান-বাম অল্টারনেট করে এই প্রক্রিয়া চালিয়ে যান যতক্ষণ না একক নম্বর বাকি থাকে। দৈর্ঘ্য n-র লিস্ট থেকে শেষে বাকি থাকা নম্বর বের করতে হবে।

উদাহরণ: n = 9 হলে ধাপগুলো:

• 1,2,3,4,5,6,7,8,9
• 2,4,6,8
• 2,6
• 6

সমাধানের ধাপগুলো:

• left := 1, head := 1, step := 1, rem := n
• rem > 1 रहने পর্যন্ত:
  • যদি left != 0 বা rem বিজোড় হয়, head := head + step
  • step := step * 2
  • left := !left
  • rem := rem / 2
• head ফেরত দিন।

উদাহরণ (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