मान लीजिए हमारे पास 1 से n तक क्रमबद्ध पूर्णांकों की एक सूची है। बाएं से शुरू करके दाएं पर समाप्त करके, हमें पहली संख्या और उसके बाद हर दूसरी संख्या को हटाना है जब तक हम सूची के अंत तक नहीं पहुंच जाते। हम पिछले चरण को फिर से दोहराएंगे, लेकिन इस बार दाएं से बाएं, सबसे दाईं संख्या और शेष संख्याओं से हर दूसरी संख्या को हटाएं। हम चरणों को फिर से दोहराएंगे, बाएं से दाएं और दाएं से बाएं बारी-बारी से, जब तक एक अकेली संख्या शेष नहीं रह जाती। हमें लंबाई n की सूची से शुरू करके अंतिम शेष संख्या ढूंढनी है।
उदाहरण के लिए, यदि इनपुट n = 9 जैसा है, तो चरण निम्नानुसार होंगे:
1,2,3,4,5,6,7,8,92,4,6,82,66
इसलिए उत्तर 6 होगा।
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
left := 1,head := 1,step := 1,rem := n- जब तक
- यदि
left शून्येतर है या rem विषम है, तोhead := head + step step := step * 2left := 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