Largest Sub Array
Given an array containing only 0’s and 1’s, Find the largest subarray containing an equal number of 0s and 1s.
Input specification:
Input 1: The length of an array.
Input 2: Array containing 0s and 1s.
Output Specification:
Return the length of the largest sub-array containing equal no. of 0s and 1s.
Example 1:
Input 1: 4
Input 2: {1,1,0,1}
Output: 2
Explanation:
The largest possible array here would be of length 2 as there should be an equal number of 0 and 1 in it. The starting index and ending index of the largest subarray is 1 and 2. Hence the output is 2.
Example 2:
Input 1: 5
Input 2: {1,1,1,1,1}
Output: 0
Explanation:
In the above example, there are no 0s in the array. Hence the output is 0.
Solution in Python 3:
#https://codewindow.in
#join our telegram channel @codewindow
def findSubArray(arr, n):
sum = 0
maxsize = -1
for i in range(0, n-1):
sum = -1 if(arr[i] == 0) else 1
for j in range(i + 1, n):
sum = sum + (-1) if (arr[j] == 0) else sum + 1
if (sum == 0 and maxsize < j-i + 1):
maxsize = j - i + 1
startindex = i
if (maxsize == -1):
print(0);
else:
print(maxsize);
size = int(input())
arr = list(map(int, input().split()))
findSubArray(arr, size)Solution in JAVA :
//https://codewindow.in
//join our telegram channel @codewindow
import java.io.*;
import java.lang.*;
import java.util.*;
class CodeWindow {
static void findSubArray(int arr[], int n)
{
int sum = 0;
int maxsize = -1, startindex = 0;
int endindex = 0;
for (int i = 0; i < n - 1; i++) {
sum = (arr[i] == 0) ? -1 : 1;
for (int j = i + 1; j < n; j++) {
if (arr[j] == 0)
sum += -1;
else
sum += 1;
if (sum == 0 && maxsize < j - i + 1) {
maxsize = j - i + 1;
startindex = i;
}
}
}
endindex = startindex + maxsize - 1;
if (maxsize == -1)
System.out.println(0);
else
System.out.println(maxsize);
}
public static void main(String[] args) throws Exception
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int size = Integer.parseInt(br.readLine());
String str[] = br.readLine().split(" ");
int arr[] = new int[size];
for(int i=0;i<size;i++)
arr[i] = Integer.parseInt(str[i]);
findSubArray(arr, size);
}
}
Solution in C++ :
//https://codewindow.in
//join our telegram channel @codewindow
#include <iostream>
using namespace std;
void findSubArray(int arr[], int n)
{
int sum = 0;
int maxsize = -1, startindex;
for (int i = 0; i < n - 1; i++) {
sum = (arr[i] == 0) ? -1 : 1;
for (int j = i + 1; j < n; j++) {
(arr[j] == 0) ? (sum += -1) : (sum += 1);
if (sum == 0 && maxsize < j - i + 1) {
maxsize = j - i + 1;
startindex = i;
}
}
}
if (maxsize == -1)
cout << 0;
else
cout << maxsize;
}
int main()
{
int size;
cin >> size;
int arr[size];
for(int i=0;i<size;i++)
cin >> arr[i];
findSubArray(arr, size);
return 0;
}Solution in C :
//https://codewindow.in
//join our telegram channel @codewindow
#include <stdio.h>
using namespace std;
void findSubArray(int arr[], int n)
{
int sum = 0;
int maxsize = -1, startindex;
for (int i = 0; i < n - 1; i++) {
sum = (arr[i] == 0) ? -1 : 1;
for (int j = i + 1; j < n; j++) {
(arr[j] == 0) ? (sum += -1) : (sum += 1);
if (sum == 0 && maxsize < j - i + 1) {
maxsize = j - i + 1;
startindex = i;
}
}
}
if (maxsize == -1)
printf("0");
else
printf("%d",maxsize);
}
int main()
{
int size;
scanf("%d",&size);
int arr[size];
for(int i=0;i<size;i++)
scanf("%d",&arr[i]);
findSubArray(arr, size);
return 0;
}Output:
5
1 1 1 1 1
0