C++を使用してすべての要素を0にするための配列に対する操作の最小数。

問題の説明

サイズNの配列があり、各要素が1または0の場合、タスクは、すべての要素をゼロに変換するために実行される操作の最小数を計算することです。以下の操作を実行できます-

要素が1の場合、その値を0に変更してから-

• 次の連続する要素が1の場合、自動的に0に変換されます

• 次の連続する要素がすでに0の場合、何も起こりません。

If arr[] = {1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1} then 4
operation are required to make all elements zero

アルゴリズム

1.If the current element is 1 then increment the count and search for the next 0 as all consecutive 1’s will be automatically converted to 0.
2. Return final count

例

#include <iostream>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;
int performMinOperation(int *arr, int n){
   int i, cnt = 0;
   for (i = 0; i < n; ++i) {
      if (arr[i] == 1) {
         int j;
         for (j = i + 1; j < n; ++j) {
            if (arr[j] == 0) {
               break;
            }
         }
         i = j - 1;
         ++cnt;
      }
   }
   return cnt;
}
int main(){
   int arr[] = {1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1};
   cout << "Minimum required operations = " << performMinOperation(arr, SIZE(arr)) << endl;
   return 0;
}

出力

上記のプログラムをコンパイルして実行する場合。次の出力を生成します-

Minimum required operations = 4