पायथन में n लोगों द्वारा फ़्लिप की गई रोशनी की संख्या की गणना करने का कार्यक्रम

मान लीजिए कि हमारे पास एक नंबर n है, मान लीजिए कि एक कमरे में n टॉगल स्विच हैं और उस कमरे में n लोग मौजूद हैं, वे इस प्रकार स्विच फ्लिप करते हैं -

व्यक्ति 1 आता है और सभी स्विच फ़्लिप करता है।
व्यक्ति 2 आता है और स्विच फ्लिप करता है जो 2:2, 4, 6, ...
मैं व्यक्ति आता हूं और स्विच को फ्लिप करता हूं जो कि i के गुणज हैं। और इसी तरह।

हमें उन स्विचों की संख्या ज्ञात करनी होगी जो अंत में चालू स्थिति में होंगे।

इसलिए, यदि इनपुट n =5 जैसा है, तो आउटपुट 2 होगा, क्योंकि प्रारंभ में बल्ब [0, 0, 0, 0, 0] हैं।

खिलाड़ी 1 के बाद:[1, 1, 1, 1, 1]
खिलाड़ी 2 के बाद [1, 0, 1, 0, 1]
खिलाड़ी 3 के बाद:[1, 0, 0, 0, 1]
खिलाड़ी 4 के बाद:[1, 0, 0, 1, 1]
खिलाड़ी 5 के बाद:[1, 0, 0, 1, 0]

अंत में 2 लाइटें चालू अवस्था में हैं

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

एल :=0
r :=n
जबकि l <=r, करते हैं
- मध्य :=l + तल (r - l)/2
- यदि मध्य * मध्य <=n <(मध्य + 1)^2, तो
  - मध्य वापसी
- अन्यथा जब n <मध्य^2, तब
  - r :=मध्य
- अन्यथा,
  - l :=मध्य + 1

उदाहरण

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

def solve(n):
   l, r = 0, n
   while l <= r:
      mid = l + (r - l) // 2
      if mid * mid <= n < (mid + 1) * (mid + 1):
         return mid
      elif n < mid * mid:
         r = mid
      else:
         l = mid + 1

n = 5
print(solve(n))