n व्यक्तियों द्वारा फ्लिप करने के बाद ऑन रहने वाले स्विच की संख्या गिनने का पायथन प्रोग्राम

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

व्यक्ति 1 उन सभी स्विच को फ्लिप करता है जो 1 के गुणक हैं (यानी सभी स्विच)।
व्यक्ति 2 उन स्विच को फ्लिप करता है जो 2 के गुणक हैं (2, 4, 6, ...)
व्यक्ति i उन स्विच को फ्लिप करता है जो 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, करें
- mid := l + (r - l) / 2
- यदि mid^2 <= n < (mid + 1)^2, तो
  - mid लौटाएं
- अन्यथा जब n < mid^2, तो
  - r := mid
- अन्यथा,
  - l := mid + 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))