पायथन में समान सेट बिट्स वाली अगली बड़ी संख्या ढूंढने का प्रोग्राम

एक संख्या n दी गई है। n से बड़ी सबसे छोटी संख्या ढूंढें जिसमें n के बराबर सेट बिट्स (1s) हों।

उदाहरण

इनपुट: n = 7 (बाइनरी: 0111)

आउटपुट: 11 (बाइनरी: 1011)

दोनों में तीन 1s हैं।

एल्गोरिदम (बिट मैनिपुलेशन)

1. copy = n, zeros = 0, ones = 0।
2. अंतिम 0s गिनें: जब तक copy सम है और शून्य नहीं, zeros++, copy >>= 1।
3. उसके बाद के 1s गिनें: जब तक copy विषम है, ones++, copy >>= 1।
4. right = ones + zeros (दाएं से पहली गैर-अंतिम स्थिति)।
5. n |= (1 << right) (वह बिट सेट करें)।
6. n &= ~((1 << right) - 1) (दाएं के सभी बिट्स क्लियर करें)।
7. n |= (1 << (ones - 1)) - 1 (सबसे कम महत्वपूर्ण बिट्स पर ones-1 1s सेट करें)।
8. n वापस करें।

पायथन कार्यान्वयन

class Solution:
    def solve(self, n):
        copy = n
        zeros = 0
        ones = 0
        
        # अंतिम 0s गिनें
        while copy and not (copy & 1):
            zeros += 1
            copy >>= 1
        
        # उसके बाद के 1s गिनें
        while copy & 1:
            ones += 1
            copy >>= 1
        
        right = ones + zeros
        n |= 1 << right              # right बिट सेट करें
        n &= ~((1 << right) - 1)     # right के दाएं सब क्लियर करें
        n |= (1 << (ones - 1)) - 1   # सबसे दाएं (ones-1) बिट्स सेट करें
        return n

# परीक्षण
ob = Solution()
print(ob.solve(7))    # 11 (0111 → 1011)
print(ob.solve(11))   # 13 (1011 → 1101)
print(ob.solve(1))    # 2 (01 → 10)
print(ob.solve(5))    # 6 (101 → 110)

समय जटिलता

• O(log n) बिट्स की संख्या के अनुपात में।
• स्थान: O(1)।

वैकल्पिक: ब्रायन कर्निघन का एल्गोरिदम

अगली संख्या = n + (n & -n) फिर बिट्स पुनर्व्यवस्थित करें। लेकिन उपरोक्त विधि मानक और स्पष्ट है।