# Find Largest Subarray with Equal Number of 0 and 1

• Write a program to find biggest sub-array having equal number of 0 and 1.

Given an array of size N which contains only 0 and 1. We have to find largest sub array containing equal number of 0 and 1.
For Example :
Input Array : 0 1 1 0 1 0, 0 1 1 1
Output : From index 0 to 7

Algorithm to find biggest sub array having equal number of 0 and 1
Let inputArray be an integer array of size N containing only 0 and 1.
• Outer for loop will fix one element(let it be K) and then inner for loop will find the sum of all sub arrays starting from K.
• While calculating sum of elements of a sub array add -1 if current element is 0 and 1 if current element is 1.
• At any time, if current sum becomes zero, then we found one sub array from K to current element which contains equal number of 0 and 1.
Time Complexity : O(n2)

## C program to find largest sub array having equal count of 0 and 1

```#include <stdio.h>
#include <limits.h>

void findMaxSubArray(int *array, int size) {
int i, j, sum = 0, maxSize = INT_MIN, left;

/* For every element array[i], find the sum of
all sub array starting form array[i] */
for(i = 0; i < size-1; i++) {
/* Here we are changing 0 to -1 */
sum = array[i] ? 1 : -1;
for (j = i+1; j < size; j++) {
if (array[j] == 1)
sum += 1;
else
sum += -1;
/* If sum is 0, that means we got equal numbers
of 0 and 1. Compare it with current maximum size */
if (sum == 0 && (maxSize < j - i + 1)) {
maxSize = j - i + 1;
left = i;
}
}
}

if (maxSize == INT_MIN) {
} else {
printf("Sub Array from index %d to %d", left, left+maxSize-1);
}
}

int main(){
int i, array = {0, 1, 1, 0, 1, 0, 0, 1, 1, 1};

findMaxSubArray(array, 10);

return 0;
}
```
Output
```Sub Array from index 0 to 7
```