C++-এ বাইনারি অ্যারেতে ০ কে ১ বদলিয়ে সর্বোচ্চ ১-এর সিকোয়েন্স (সেট-২)

কনসেপ্ট

০ এবং ১-এর অ্যারে দেওয়া আছে। কোন ০ কে ১ বদলিয়ে সর্বোচ্চ দৈর্ঘ্যের ১-এর কন্টিনিউাস সিকোয়েন্স পাওয়া যায় তা খুঁজে বের করুন। টাইম কমপ্লেক্সিটি O(n), স্পেস O(1)।

ইনপুট ১

arr[] = {1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1}

আউটপুট ১

Index 10

ইনডেক্স ১০-এ ০ কে ১ বদলিয়ে সর্বোচ্চ ১-এর সিকোয়েন্স পাওয়া যায়।

ইনপুট ২

arr[] = {1, 1, 1, 1, 1, 0}

আউটপুট ২

Index 5

পদ্ধতি

প্রতিটি ০-এর বাম ও ডান পাশের ১-এর গণনা রাখুন। ভেরিয়েবল: leftCnt, rightCnt, maxIndex, lastInd, maxCnt।

1. rightCnt বাড়াতে থাকুন ১ পাওয়া পর্যন্ত। ০ পেলে চেক করুন প্রথম ০ কিনা (lastInd == -1)।
2. প্রথম ০ হলে lastInd = i, leftCnt = rightCnt, rightCnt = 0।
3. পরবর্তী ০ পেলে leftCnt + rightCnt + 1 দিয়ে maxCnt আপডেট করুন। lastInd = i, leftCnt = rightCnt, rightCnt = 0।
4. লুপ শেষে lastInd-এর জন্য চেক করুন। ফলাফল maxIndex-এ থাকবে।

উদাহরণ (C++ কোড)

// C++ প্রোগ্রাম: ০ কে ১ বদলিয়ে সর্বোচ্চ ১-এর সিকোয়েন্স
#include <bits/stdc++.h>
using namespace std;

int maxOnesIndex(bool arr1[], int n1) {
    int i = 0, leftCnt1 = 0, rightCnt1 = 0, maxIndex1 = -1, lastInd1 = -1, maxCnt1 = 0;
    while (i < n1) {
        if (arr1[i]) rightCnt1++;
        else {
            if (lastInd1 != -1) {
                if (rightCnt1 + leftCnt1 + 1 > maxCnt1) {
                    maxCnt1 = leftCnt1 + rightCnt1 + 1;
                    maxIndex1 = lastInd1;
                }
            }
            lastInd1 = i;
            leftCnt1 = rightCnt1;
            rightCnt1 = 0;
        }
        i++;
    }
    if (lastInd1 != -1) {
        if (leftCnt1 + rightCnt1 + 1 > maxCnt1) {
            maxCnt1 = leftCnt1 + rightCnt1 + 1;
            maxIndex1 = lastInd1;
        }
    }
    return maxIndex1;
}

int main() {
    bool arr1[] = {1,1,0,0,1,0,1,1,1,1,0,1,1};
    int n1 = sizeof(arr1)/sizeof(arr1[0]);
    cout << "০ কে ১ বদলির ইনডেক্স: " << maxOnesIndex(arr1, n1);
    return 0;
}

আউটপুট

০ কে ১ বদলির ইনডেক্স: 10