C++ में एक फ्लिप के साथ बाइनरी प्रतिनिधित्व में 1s की सबसे लंबी सीक्वेंस ढूंढें

मान लीजिए हमारे पास एक पूर्णांक n है। इसके अंदर, हम सबसे लंबी 1s की सीक्वेंस जनरेट करने के लिए एक बिट फ्लिप कर सकते हैं। मान लीजिए संख्या 13 है, तो बाइनरी प्रतिनिधित्व 1101 है। यदि हम एक बिट फ्लिप करते हैं जैसे 0 को 1 बनाते हैं, तो यह 1111 हो जाएगा। यह 1s की सबसे लंबी सीक्वेंस है

इस समस्या को हल करने के लिए, हम दी गई संख्या के बिट्स के माध्यम से चलेंगे। हम वर्तमान 1s की सीक्वेंस लंबाई, और पिछली 1s की सीक्वेंस लंबाई को ट्रैक करेंगे। जब एक शून्य मिला है, तो पिछली लंबाई अपडेट करें। तो यदि अगला बिट 1 है, तो पिछली लंबाई को वर्तमान लंबाई पर सेट करना चाहिए। यदि अगला 0 है, तो पिछली को फिर से 0 बनाएं।

उदाहरण

#include 
using namespace std;

int singleFlipMaxOnes(unsigned number) {
    if (~number == 0)
        return 8*sizeof(int);
    int curr = 0, prev = 0, max_size = 0;
    while (number!= 0) {
        if ((number & 1) == 1)
            curr++;
        else if ((number & 1) == 0) {
            prev = (number & 2) == 0? 0 : curr;
            curr = 0;
        }
        max_size = max(prev + curr, max_size);
        number >>= 1;
    }
    return max_size+1;
}

int main() {
    cout << "Maximum length of the sequence with 1s: " << singleFlipMaxOnes(13);
}

आउटपुट

Maximum length of the sequence with 1s: 4