Minimum number of operations on an array to make all elements 0 using C++.

Problem statement

Given an array of size N and each element is either 1 or 0. The task is to calculated the minimum number of operations to be performed to convert all elements to zero. One can perform below operations −

If an element is 1, You can change its value equal to 0 then −

• If the next consecutive element is 1, it will automatically get converted to 0

• If the next consecutive element is already 0, nothing will happen.

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

Algorithm

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

Example

#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; }

Output

When you compile and execute the above program. It generates the following output −

Minimum required operations = 4