C Exercises: Find the largest subarray with equal number of 0s and 1s

Last update on March 18 2025 13:21:12 (UTC/GMT +8 hours)

62. Largest Subarray with Equal 0s and 1s

Write a program in C to find the largest subarray with an equal number of 0s and 1s.

Expected Output :
The given array is : 0 1 0 0 1 1 0 1 1 1
Subarray found from the index 0 to 7

To find the largest subarray with an equal number of 0s and 1s, the program converts 0s to -1s and then uses a hashmap to track the cumulative sums. By identifying subarrays where the cumulative sum is the same at different indices, the program can determine the largest subarray with equal 0s and 1s. This approach efficiently finds the required subarray by leveraging the properties of cumulative sums.

Visual Presentation:

C Exercises: Find the largest subarray with equal number of 0s and 1s.

Sample Solution:

C Code:

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

// Function to find the largest subarray with an equal count of 0s and 1s
void findLrgSubArray(int *arr1, int arr_size) {
int i, j, sum = 0, lrgSize = INT_MIN, left;

    // Loop through the array to find the largest subarray
for (i = 0; i < arr_size - 1; i++) {
sum = arr1[i] ? 1 : -1; // Assigns a value based on the element (1 or -1)

        // Nested loop to calculate the sum for each subarray
for (j = i + 1; j < arr_size; j++) {
if (arr1[j] == 1)
sum += 1;
else
sum += -1;

            // Check if the sum is 0 and if the subarray size is the largest so far
if (sum == 0 && (lrgSize < j - i + 1)) {
lrgSize = j - i + 1;
left = i; // Store the starting index of the subarray
            }
        }
    }

    // Check if a subarray with equal 0s and 1s is found
if (lrgSize == INT_MIN) {
printf("No such subarray found from the given array.");
    } else {
printf("Subarray found from the index %d to %d", left, left + lrgSize - 1);
    }
}

int main() {
int i, arr1[] = {0, 1, 0, 0, 1, 1, 0, 1, 1, 1};
int n = sizeof(arr1) / sizeof(arr1[0]);

    //------------- print original array ------------------	
printf("The given array is :  ");
for (i = 0; i < n; i++) {
printf("%d  ", arr1[i]);
    }
printf("\n");
    //------------------------------------------------------

    // Find and display the largest subarray with an equal count of 0s and 1s
findLrgSubArray(arr1, n);
return 0;
}

Sample Output:

The given array is :  0  1  0  0  1  1  0  1  1  1  
Subarray found from the index 0 to 7

Flowchart:/p>

For more Practice: Solve these Related Problems:

Write a C program to find the longest subarray with an equal number of 0s and 1s using a hash map approach.
Write a C program to detect the subarray with equal 0s and 1s by converting 0s to -1s and applying Kadane’s algorithm.
Write a C program to print all subarrays with equal numbers of 0s and 1s along with their indices.
Write a C program to find the maximum length subarray with equal 0s and 1s using prefix sums.

C Programming Code Editor:

Previous: Write a program in C to find maximum product subarray in a given array.
Next: Write a program in C to replace every element with the greatest element on its right side.