ঠিক kটি বিজোড় সংখ্যা সম্বলিত সবচেয়ে বড় সাব-অ্যারে খুঁজে বের করা C++-তে

মনে করুন আমাদের n উপাদান সম্বলিত একটি অ্যারে আছে। সমস্যাটি হল ঠিক kটি বিজোড় সংখ্যা সম্বলিত সবচেয়ে বড় সাব-অ্যারে খুঁজে বের করা। তাই যদি A = [2, 3, 4, 11, 4, 12, 7], এবং k = 1 হয়, তবে আউটপুট হবে 4, সাব-অ্যারে হল [4, 11, 4, 12]

আমরা স্লাইডিং উইন্ডো ব্যবহার করে এটি সমাধান করতে পারি। কাজটি নিচের মতো -

• max := 0, count := 0, এবং start := 0 ইনিশিয়ালাইজ করুন
• i = 0 থেকে n-1 পর্যন্ত, নিচের কাজগুলো করুন
  • যদি arr[i] mod 2 শূন্য নয়, তবে count ১ বাড়ান
  • যতক্ষণ count > k এবং start <= i, নিচের কাজগুলো করুন
    • যদি arr[start] mod 2 শূন্য নয়, তবে count ১ কমান
    • start ১ বাড়ান
  • যদি count = k হয়, তবে
    • যদি max < (i - start + 1), তবে max := (i - start + 1)
  • max রিটার্ন করুন

উদাহরণ

#include <iostream>
using namespace std;

int oddSubarrayMaxLength(int arr[], int n, int k) {
    int max_len = 0, count = 0, start = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] % 2 != 0)
            count++;
        while (count > k && start <= i)
            if (arr[start++] % 2 != 0)
                count--;
        if (count == k)
            if (max_len < (i - start + 1))
                max_len = i - start + 1;
    }
    return max_len;
}

int main() {
    int arr[] = {2, 3, 4, 11, 4, 12, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 1;
    cout << "Maximum Length is: " << oddSubarrayMaxLength(arr, n, k);
}

আউটপুট

Maximum Length is: 4