ठीक 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 को 1 से बढ़ाएं
  • जब count > k और start <= i, तो निम्नलिखित करें
    • यदि arr[start] mod 2 शून्य नहीं है, तो count को 1 से घटाएं
    • start को 1 से बढ़ाएं
  • यदि 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