अजगर में n व्यक्तियों द्वारा फ़्लिप करने के बाद चालू होने वाले स्विच की संख्या की गणना करने का कार्यक्रम

मान लीजिए कि हमारे पास एक नंबर n है, और एक कमरे में n स्विच हैं, और सभी स्विच बंद हैं। अब n लोग जो फ्लिप करते हैं वे निम्नानुसार स्विच करते हैं -

• व्यक्ति 1 सभी स्विच को फ़्लिप करता है जो 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, 0] किया, व्यक्ति 4 ने [1, 0, 0, 1, 0] किया।>

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

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

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

उदाहरण

class Solution:
   def solve(self, 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

ob = Solution()
n = 5
print(ob.solve(n))

इनपुट

5

आउटपुट

2