सी ++ में एक फ्लिप के साथ बाइनरी प्रतिनिधित्व में 1 का सबसे लंबा अनुक्रम खोजें

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

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

उदाहरण

#include<iostream>
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