Home/Questions/Q 803888
Next
In Process
codemania
  • 0
Asked: 2023-05-27T09:33:29+00:00 In:

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

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

    1 Answer

    1. 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.

       

      2. // Java Program to Find the Largest sub-Array 
      3. // Consisting of Equal Number of 0's and 1's
      4. import java.io.BufferedReader;
      5. import java.io.InputStreamReader;
      7. public class EqualZeroesAndOnes {
      8.     // Function to find out the largest subarray having equal zeroes and ones.
      9.     static int[] largestSubarray(int[] array){
      10.         int[] index = new int[2];
      11.         int start,end,i;
      12.         start = end = -1;
      13.         boolean flag = true;
      14.         for(i=0; i<array.length; i++){
      15.             if (array[i] == 0 || array[i] == 1){
      16.                 if(start == -1){
      17.                     start = i;
      18.                     flag = false;
      19.                 }
      20.                 else if (flag){
      21.                     flag = false;
      22.                 }
      23.                 else{
      24.                     flag = true;
      25.                     end = i;
      26.                 }
      27.             }
      28.         }
      29.         if(start != -1 && end != -1){
      30.             index[0] = start;
      31.             index[1] = end;
      32.         }
      33.         return index;
      34.     }
      35.     // Function to read the input and to display the subarray
      36.     public static void main(String[] args) {
      37.         BufferedReader br = new BufferedReader
      38.                             (new InputStreamReader(System.in));
      39.         int size;
      40.         System.out.println("Enter the size of the array");
      41.         try {
      42.             size = Integer.parseInt(br.readLine());
      43.         } catch (Exception e) {
      44.             System.out.println("Invalid Input");
      45.             return;
      46.         }
      47.         int[] array = new int[size];
      48.         System.out.println("Enter array elements");
      49.         int i;
      50.         for (i = 0; i < array.length; i++) {
      51.             try {
      52.                 array[i] = Integer.parseInt(br.readLine());
      53.             } catch (Exception e) {
      54.                 System.out.println("An error occurred");
      55.             }
      56.         }
      57.         int[] index = largestSubarray(array);
      58.         if(index[0] == 0 && index[1] == 0)
      59.             System.out.println("No such subarray exists");
      60.         else{
      61.             for(i=index[0]; i<=index[1]; i++){
      62.                 System.out.print(array[i] + " ");
      63.             }
      64.         }
      65.     }
      66. }
      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.
       
      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
      • 0
    You must login to add an answer.
    Need An Account, 
    Related Questions