Minimum toggles to partition a binary array so that it has first 0s then 1s - GeeksforGeeks

Minimum toggles to partition a binary array so that it has first 0s then 1s - GeeksforGeeks
Given an array of n integers containing only 0 and 1. Find the minimum toggles (switch from 0 to 1 or vice-versa) required such the array the array become partitioned, i.e., it has first 0s then 1s. There should be at least one 0 in the beginning, and there can be zero or more 1s in the end.

Let zero[i] denotes the number of 0's till ith
index, then for each i, minimum number of
toggles required can be written as: i - zero[i]
 + zero[n] - zero[i] . The part i - zero[i]
indicates number of 1's to be toggled and the 
part zero[n] - zero[i] indicates number of 0's
to be toggled.

After that we just need to take minimum of 
all to get the final answer.

int minToggle(int arr[], int n)

{

    int zero[n+1];

    zero[0] = 0;

 

    // Fill entries in zero[] such that zero[i]

    // stores count of zeroes to the left of i

    // (exl

    for (int i=1; i<=n; ++i)

    {

        // If zero found update zero[] array

        if (arr[i-1] == 0)

            zero[i] = zero[i-1] + 1;

        else

            zero[i] = zero[i-1];

    }

 

    // Finding the minimum toggle required from

    // every index(0 to n-1)

    int ans = n;

    for (int i=1; i <= n; ++i)

        ans = min(ans, i-zero[i]+zero[n]-zero[i]);

 

    return ans;

}

Read full article from Minimum toggles to partition a binary array so that it has first 0s then 1s - GeeksforGeeks