Java Program to Find the Largest Subarray with Equal Number of 0s and 1s

This is the Java Program to Find the Largest sub-Array consisting of Equal Number of 0’s and 1’s.

Problem Description

Given an array, find out the longest subarray consisting of the equal number of zeroes and ones.

Example:
ArrayOne = [1, 2, 0, 5, 6, 0, 1, 0]

Output
1 2 0 5 6 0 1

Problem Solution

Maintain two variables start and end to store the starting and ending index of the subarray and initialize them to -1. Also, create a boolean variable flag mark it to be true. Iterate through the array, and check if the element is 0 or 1 if it is one and the flag is true set the flag to false, otherwise set the flag to true and update the variables starting and ending indexes.

Program/Source Code

Here is the source code of the Java Program to Find the Largest sub-Array consisting of Equal Number of 0’s and 1’s. The program is successfully compiled and tested using IDE IntelliJ Idea in Windows 7. The program output is also shown below.

```
 
```

// Java Program to Find the Largest sub-Array

// Consisting of Equal Number of 0's and 1's

```
import java.io.BufferedReader;
```
```
import java.io.InputStreamReader;
```
```
 
```
```
public class EqualZeroesAndOnes {
```

    // Function to find out the largest subarray having equal zeroes and ones.

    static int[] largestSubarray(int[] array){

```
        int[] index = new int[2];
```
```
        int start,end,i;
```
```
        start = end = -1;
```
```
        boolean flag = true;
```
```
        for(i=0; i<array.length; i++){
```

            if (array[i] == 0 || array[i] == 1){

```
                if(start == -1){
```
```
                    start = i;
```
```
                    flag = false;
```
```
                }
```
```
                else if (flag){
```
```
                    flag = false;
```
```
                }
```
```
                else{
```
```
                    flag = true;
```
```
                    end = i;
```
```
                }
```
```
            }
```
```
        }
```
```
        if(start != -1 && end != -1){
```
```
            index[0] = start;
```
```
            index[1] = end;
```
```
        }
```
```
        return index;
```
```
    }
```

    // Function to read the input and to display the subarray

    public static void main(String[] args) {

        BufferedReader br = new BufferedReader

                            (new InputStreamReader(System.in));

```
        int size;
```

        System.out.println("Enter the size of the array");

```
        try {
```

            size = Integer.parseInt(br.readLine());

```
        } catch (Exception e) {
```

            System.out.println("Invalid Input");

```
            return;
```
```
        }
```
```
        int[] array = new int[size];
```

        System.out.println("Enter array elements");

```
        int i;
```

        for (i = 0; i < array.length; i++) {

```
            try {
```

                array[i] = Integer.parseInt(br.readLine());

```
            } catch (Exception e) {
```

                System.out.println("An error occurred");

```
            }
```
```
        }
```

        int[] index = largestSubarray(array);

        if(index[0] == 0 && index[1] == 0)

            System.out.println("No such subarray exists");

```
        else{
```

            for(i=index[0]; i<=index[1]; i++){

                System.out.print(array[i] + " ");

```
            }
```
```
        }
```
```
    }
```
```
}
```

Program Explanation

1. In function largestSubarray(), the variables start and end are initialized to -1 and flag is set to true.
2. The loop for(i=0; i<array.length; i++) is used to iterate through the array.
3. The condition if(array[i] == 0 || array[i] == 1) checks for zero and one.
4. The nested condition if(start == -1) checks if the current element is the first element of the subarray.
5. The nested condition else if(flag) checks if the number of zeroes and ones were previously equal.
6. The else part sets the end variable to point to the last entry of the subarray.

Time Complexity: O(n) where n is the number of elements in the array.

Note: Join free Sanfoundry classes at Telegram or Youtube

Runtime Test Cases

 
Case 1 (Positive Test Case):
 
Enter the size of the array
8
Enter array elements
1
2
0
5
6
0
1
0
1 2 0 5 6 0 1 
 
Case 2 (Negative Test Case):
 
Enter the size of the array
5
Enter array elements
1
2
3
4
5
No such subarray exists

Sanfoundry Global Education & Learning Series – Java Programs.

« Prev - Java Program to Check if an Array is Decreasing

» Next - Java Program to Count the Number of Unique Words

Related Posts:

Recommended Articles: