Philipp
0
Q:

You are Given an array containing only 0s and 1s, find the largest subarray which contain equal no of 0s and 1s

#include <iostream> 
using namespace std; 
  
// This function Prints the starting and ending 
// indexes of the largest subarray with equal 
// number of 0s and 1s. Also returns the size 
// of such subarray. 
  
int findSubArray(int arr[], int n) 
{ 
    int sum = 0; 
    int maxsize = -1, startindex; 
  
    // Pick a starting point as i 
    for (int i = 0; i < n - 1; i++) { 
        sum = (arr[i] == 0) ? -1 : 1; 
  
        // Consider all subarrays starting from i 
        for (int j = i + 1; j < n; j++) { 
            (arr[j] == 0) ? (sum += -1) : (sum += 1); 
  
            // If this is a 0 sum subarray, then 
            // compare it with maximum size subarray 
            // calculated so far 
            if (sum == 0 && maxsize < j - i + 1) { 
                maxsize = j - i + 1; 
                startindex = i; 
            } 
        } 
    } 
    if (maxsize == -1) 
        cout << "None"<<endl; 
    else
        cout << startindex <<" "<< startindex + maxsize - 1<<endl; 
  
    return maxsize; 
} 
  
/* Driver code*/
int main() 
{   int t;
    cin>>t;
    while(t--)
    { int n;
      cin>>n;
    int arr[n];
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
    }
    
    findSubArray(arr,n); 
    }
    return 0; 
} 
  
0

New to Communities?

Join the community