पाइथन में आखिरी गुब्बारा प्राप्त करने वाले बच्चे की शुरुआती अनुक्रमणिका खोजने का कार्यक्रम?

मान लीजिए कि हमारे पास n बच्चे एक घेरे में खड़े हैं, और वे एक गुब्बारा लेने की प्रतीक्षा कर रहे हैं। वितरण kth बच्चे (पहले सूचकांक 0 पर) से शुरू होता है, और उन्हें एक गुब्बारा देकर वे सर्कल छोड़ देते हैं। अब प्रत्येक kth बच्चे को एक गुब्बारा दक्षिणावर्त जाता है जब तक कि केवल एक बच्चा बचा हो जिसे गुब्बारा मिलता है। इसलिए यदि हमारे पास n और k है, तो हमें उस बच्चे का प्रारंभिक सूचकांक ज्ञात करना होगा जो अंतिम गुब्बारा प्राप्त करता है।

इसलिए, यदि इनपुट n =3 k =2 जैसा है, तो आउटपुट 1 होगा, पहले दौर में, बच्चे 2 को एक गुब्बारा मिलता है, और छोड़ दें तो सर्कल [0, 1] होगा। दूसरे दौर में, बच्चे 0 को एक गुब्बारा मिलता है, वृत्त [1] होगा।

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

arr :=0 से n तक की एक नई सूची
init :=0
जबकि गिरफ्तारी का आकार> 1, करो
- निकालें :=(init + k) गिरफ्तारी का आधुनिक आकार
- गिरफ्तारी हटाएं[निकालें]
- init :=हटाएं
वापसी गिरफ्तारी[0]

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें:

उदाहरण

class Solution:
   def solve(self, n, k):
      arr = list(range(0, n))
      init = 0
      while len(arr) > 1:
         remove = (init + k) % len(arr)
         del arr[remove]
         init = remove
      return arr[0]

ob = Solution()
n = 3
k = 2
print(ob.solve(n, k))

इनपुट

3,2