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.
Read full article from 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;}