पायथन में n लोगों द्वारा फ्लिप किए गए ऑन लाइट्स की संख्या गिनने का प्रोग्राम

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

व्यक्ति 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, 1]
खिलाड़ी 4 के बाद: [1, 0, 0, 1, 1]
खिलाड़ी 5 के बाद: [1, 0, 0, 1, 0]

अंत में 2 लाइट्स ऑन स्टेट में हैं।

मुख्य अंतर्दृष्टि

एक स्विच उतनी बार फ्लिप होता है जितने उसके डिवाइजर होते हैं। केवल पूर्ण वर्ग संख्याओं के डिवाइजर की संख्या विषम होती है। इसलिए उत्तर floor(sqrt(n)) है।

एल्गोरिदम (बाइनरी सर्च)

l := 0, r := n
while l <= r:
- mid := l + (r - l) // 2
- यदि mid * mid <= n < (mid + 1)^2, तो mid लौटाएं
- अन्यथा यदि n < mid^2, तो r := mid
- अन्यथा, l := mid + 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))  # आउटपुट: 2