C++ में एलिमिनेशन गेम

मान लीजिए कि हमारे पास 1 से n तक क्रमबद्ध पूर्णांकों की एक सूची है। यानी बाएं से शुरू होकर दाएं पर समाप्त होने पर, हमें सूची के अंत तक पहुंचने तक पहले नंबर और बाद में हर दूसरे नंबर को हटाना होगा। हम पिछले चरण को फिर से दोहराएंगे, लेकिन इस बार दाएं से बाएं, सबसे दाएं नंबर और बाकी सभी नंबरों को हटा दें। हम फिर से चरणों को दोहराएंगे, बारी-बारी से बाएं से दाएं और दाएं से बाएं, जब तक कि एक एकल संख्या न रह जाए। हमें अंतिम संख्या ज्ञात करनी है जो n लंबाई की सूची से शुरू होती है।

तो अगर इनपुट n =9 जैसा है, तो चरण इस प्रकार होंगे -

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

• 2,4 ,6,8

• 2 ,6

• 6

तो उत्तर 6 होगा।

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

• बाएं:=1, सिर:=1, चरण:=1, रेम:=n

• जबकि रेम> 1

  • यदि बाईं ओर शून्य नहीं है या रेम विषम है, तो सिर:=सिर + चरण

  • चरण:=चरण * 2

  • बाएँ :=बाएँ का उलटा

  • रेम :=रेम / 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