C++を使用してm個の奇数のサブ配列の数を見つける

C ++を使用したことがある場合は、サブアレイとは何か、およびそれらがどれほど有用であるかを知っている必要があります。ご存知のように、C ++では、複数の数学的な問題を簡単に解決できます。したがって、この記事では、C++でこれらのサブ配列を使用してM個の奇数を見つける方法に関する完全な情報を説明します。

この問題では、与えられた配列と整数mで形成された多くのサブ配列を見つける必要があります。各サブ配列には正確にm個の奇数が含まれています。したがって、これがこのアプローチの簡単な例です-

Input : array = { 6,3,5,8,9 }, m = 2
Output : 5
Explanation : Subarrays with exactly 2 odd numbers are
{ 3,5 }, { 6,3,5 }, { 3,5,8 }, { 5,8,9 }, { 6,3,5,8 }, { 3,5,8,9 }

Input : array = { 1,6,3,2,5,4 }, m = 2
Output : 6
Explanation : Subarrays with exactly 2 odd numbers are
{ 1,6,3 }, { 3,2,5 }, { 1,6,3,2 }, { 6,3,2,5 }, { 3,2,5,4 }, { 6,3,2,5,4 }

最初のアプローチ

このアプローチでは、すべての可能なサブ配列が特定の配列から生成され、各サブ配列が正確にm個の奇数であるかどうかがチェックされます。これは単純な生成と検索のアプローチであり、このアプローチの時間計算量はO（n ² です。 。

例

#include <bits/stdc++.h>
using namespace std;
int main (){
    int a[] = { 1, 6, 3, 2, 5, 4 };
    int n = 6, m = 2, count = 0; // n is size of array, m numbers to be find in subarrays,
                              // count is number of subarray with m odd numbers
    for (int i = 0; i < n; i++){ // outer loop to process each element.
        int odd = 0;
        for (int j = i; j < n; j++) {// inner loop to find subarray with m number
            if (a[j] % 2)
                odd++;
            if (odd == m) // if odd numbers become equals to m.
                count++;
        }
    }
    cout << "Number of subarrays with n numbers are: " << count;
    return 0;
}

出力

Number of subarrays with n numbers are: 6

上記のコードの説明

このコードでは、ネストされたループを使用してm個の奇数のサブ配列を検索し、外側のループを使用して「i」をインクリメントします。これは、配列内の各要素を処理するために使用されます。

内側のループは、奇数カウンターがmに達するまでサブアレイと処理要素を検索するために使用され、検出された各サブアレイの結果カウンターカウントを増やし、最後にカウント変数に格納された結果を出力します。

2番目のアプローチ

別のアプローチは、「i」の奇数のプレフィックスの数を格納するための配列を作成し、すべての要素を処理し、見つかったすべての奇数の奇数の数を増やすことです。

奇数の数がmを超えるか、mに等しくなった場合は、プレフィックス配列の（odd --m）の位置にある数を追加します。

奇数がm以上になると、インデックスと「奇数-m」の数値がカウント変数に追加されるまでに形成されたサブアレイの数を計算します。すべての要素が処理された後、結果はカウント変数に保存されます。

例

#include <bits/stdc++.h>
using namespace std;
int main (){
    int array[ ] = { 1, 6, 3, 2, 5, 4 };
    int n = 6, m = 2, count = 0, odd = 0, i;
    int prefix_array[n + 1] = { 0 };
    // outer loop to process every element of array
    for (i = 0; i < n; i++){
        prefix_array[odd] = prefix_array[odd] + 1;    // implementing value at odd index in prefix_array[ ]
        // if array element is odd then increment odd variable
        if (array[i] % 2 == 0)
            odd++;
        // if Number of odd element becomes equal or greater than m
        //  then find the number of possible subarrays that can be formed till the index.
        if (odd >= m)
            count += prefix_array[odd - m];
    }
    cout << "Number of subarrays with n numbers are: " << count;
    return 0;
}

出力

Number of subarrays with n numbers are: 6

上記のコードの説明

開始値を使用して配列と変数を初期化する-

int array[ 6 ] = { 1, 6, 3, 2, 5, 4 };
int n = 6, m = 2, count = 0, odd = 0, i;
int prefix_array[n + 1] = { 0 };

ここでは、変数nを配列のサイズで初期化し、mを奇数の数で初期化し、0でカウントして可能なサブ配列のカウントを維持し、奇数を0で、prefix_arrayのサイズをn+1で0にします。

ループを理解する

for (i = 0; i < n; i++){
   prefix_array[odd] = prefix_array[odd] + 1;
   if (array[i] % 2 == 0)
      odd++;
      if (odd >= m)
         count += prefix_array[odd - m];
}

このループでは、prefix_array []の奇数インデックスに値を実装し、奇数が見つかった場合は奇数変数をインクリメントします。サブ配列の数は、奇数の変数がm以上になるインデックスまで形成できることがわかります。

最後に、カウント変数に格納されたm個の奇数を含むいくつかのサブ配列を出力して出力を取得します。

結論

この記事では、2つのアプローチからm個の奇数を持つサブアレイの数を見つけるアプローチを理解しています-

• すべてのサブアレイを生成し、その中のm個の奇数をチェックし、見つかった各サブアレイのカウントをインクリメントします。このコードの時間計算量はO（n2）です。

• 配列の各要素を調べてプレフィックス配列を作成し、プレフィックス配列を使用して結果を見つける効率的なアプローチ。このコードの時間計算量はO（n）です。

この記事が問題と解決策を理解するのに役立つことを願っています。