Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

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


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

उदाहरण के लिए, यदि इनपुट n = 9 जैसा है, तो चरण निम्नानुसार होंगे:

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

इसलिए उत्तर 6 होगा।

इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:

  • left := 1, head := 1, step := 1, rem := n
  • जब तक
    • यदि left शून्येतर है या 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

  1. C++ में जंप गेम IV C++ में जंप गेम IV

    मान लीजिए हमारे पास arr नामक पूर्णांकों की एक सरणी है। हम प्रारंभ में इंडेक्स 0 पर हैं। एक चरण में हम इंडेक्स i से i + x पर कूद सकते हैं जहां: i + x = 0, j जहां: arr[i] और arr[j] समान हैं और i और j समान नहीं हैं। यहां n सरणी का आकार है। हमें सरणी के अंतिम इंडेक्स तक पहुंचने के लिए न्यूनतम चरणों की स

  1. C++ में जंप गेम V C++ में जंप गेम V

    मान लीजिए हमारे पास arr नामक पूर्णांकों की एक सरणी और एक पूर्णांक d है। एक चरण में हम इंडेक्स i से कूद सकते हैं: i + x जहां: i + x < n और x की सीमा 1 से d है। = 0 और x की सीमा 1 से d है। arr[k] हो। हम सरणी के किसी भी इंडेक्स से कूदना शुरू कर सकते हैं। हमें अधिकतम इंडेक्स की संख्या ज्ञात करनी है ज

  1. C++ में अधिकतम बाइनरी ट्री निर्माण C++ में अधिकतम बाइनरी ट्री निर्माण

    मान लीजिए हमारे पास एक पूर्णांक सरणी है जिसके सभी तत्व अद्वितीय हैं। एक अधिकतम बाइनरी ट्री निम्न नियमों से बनता है: रूट सरणी का अधिकतम तत्व होता है। बायाँ सबट्री अधिकतम तत्व के बाएँ भाग से बने सबसरणी का अधिकतम ट्री होता है। दायाँ सबट्री अधिकतम तत्व के दाएँ भाग से बने सबसरणी का अधिकतम ट्री होता है।