You are given an array of integers ARR[] of size N consisting of zeros and ones. You have to select a subset and flip bits of that subset. You have to return the count of maximum one’s that you can obtain by flipping chosen sub-array at most once.
A flip operation is one in which you turn 1 into 0 and 0 into 1.
For example:
If you are given an array {1, 1, 0, 0, 1} then you will have to return the count of maximum one’s you can obtain by flipping anyone chosen sub-array at most once, so here you will clearly choose sub-array from the index 2 to 3 and then flip it's bits. So, the final array comes out to be {1, 1, 1, 1, 1} which contains five ones and so you will return 5.
The first line of input consists of a single integer T denoting the total number of the test case.
The first line of each test case contains an integer N, which represents the array's size.
The second line of each test case contains N space-separated integers representing the array elements accordingly.
For each test case, return a single integer representing the maximum number of 1's you can have in the array after at most one flip operation.
You don’t have to print anything; it has already been taken care of. Just implement the given function.
1 <= T = 100
1 <= N <= 10^4
0 <= ARR[i] <= 1
Time Limit: 1 sec
3
5
1 0 0 1 0
4
1 1 1 0
5
0 0 1 0 0
4
4
4
For the first test case:
We can perform a flip operation in the range [1,2]. After the flip operation, the array is: 1 1 1 1 0
and so the answer will be 4
Similarly, in the second test case :
We can perform a flip operation in the range [3,3]. After the flip operation, the array is: 1 1 1 1
and so the answer will be 4.
Finally for the third test case :
We can perform a flip operation in the range [0,4]
After the flip operation, the array is: 1 1 0 1 1
and so the answer will be 4
3
5
0 0 0 0 0
5
1 1 1 1 1
8
1 0 1 0 1 0 1 0
5
5
5
Try and think about how you will know which bits need to be flipped.
The idea is to check for all the possible subarrays and inside each subarray, check for the highest value of the difference between the count for zeroes and ones for this. Let’s consider this highest difference to be MAX and initialize it to zero so formally MAX = count of zeroes in that subarray - count of ones in the same subarray.
O(N ^ 2), Where ‘N’ denotes the number of elements in the Array
Since we are using two nested loops.
O(1)
We are using constant space.
All tags
Sort by
Interview problems
Flip Bits(with 98.88%)Accurate
import java.util.* ;
import java.io.*;
public class Solution {
public static int flipBits(int[] arr,int n) {
//Write your code here
int count = 0;
for(int i=0;i<arr.length;i++){
if(arr[i]==0){
arr[i] = 1;
}else{
arr[i] = -1;
count++;
}
}
int sum=Integer.MIN_VALUE, curSum = 0;
for(int i=0;i<n;i++){
curSum+=arr[i];
sum = Math.max(curSum, sum);
if(curSum<0)
curSum = 0;
}
if(sum<0){
sum=0;
}
return sum+count;
}
}
Interview problems
simple c++ soln:
#include <bits/stdc++.h>
//simple apply the kadane's algo to solve these problem
int flipBits(int* arr, int n)
{
int count=0;// to count the number of 1's in input arr;
for (int i=0;i<n;i++)
if(arr[i]==1) {arr[i]=-1; count++;}
else arr[i]=1;
int sum=0;
int ans=0;
for (int i=0;i<n;i++)
{
sum+=arr[i];
ans=max(ans,sum);
if(sum<0) sum=0;
}
return count+ans;
}
Interview problems
Converted the problem into maximum sub array sum
I used kadane algorithm to find this…
Interview problems
python solution
a=arr.count(1)
s=0
maxsum=0
for i in range(0,len(arr)):
if(arr[i]==0):
arr[i]=1
else:
arr[i]=-1
for i in range(0,len(arr)):
s=s+arr[i]
if(s<0):
s=0
else:
maxsum=max(maxsum,s)
return maxsum+a
Interview problems
simple c++ || kadane's algorithms
#include <bits/stdc++.h>
int flipBits(int* arr, int n)
{
// WRITE YOUR CODE HERE
int cntone=0;
for(int i=0;i<n;i++)
{
if(arr[i]==0)
{
arr[i]=1;
}
else
{
cntone++;
arr[i]=-1;
}
}
int maxi=0;
int sum=0;
for(int i=0;i<n;i++)
{
sum=sum+arr[i];
if(sum<0)
{
sum=0;
}
if(sum>=maxi)
{
maxi=sum;
}
}
return maxi+cntone;
}
Interview problems
The flip Bits problem (arrays)
I have created a code to address the given problem, however, it is not passing the test cases. Could you please provide me with any suggestions for bug fixes?
import java.util.* ;
import java.io.*;
public class Solution {
public static int flipBits(int[] arr,int n) {
int originalzeroes=0;
int currentMax = 0;
int maxDiff = 0;
for (int i = 0; i < n; i++) {
if (arr[i] == 0)
originalzeroes++;
int val = (arr[i]==1)?1:-1;
currentMax = Math.max(val,currentMax+val);
maxDiff = Math.max(maxDiff,currentMax);
}
maxDiff = Math.max(0,maxDiff);
return maxDiff+originalzeroes;
}
}
Interview problems
Java O(N)
public static int flipBits(int[] arr,int n) {
//Write your code here
int count_1=0;
for(int i=0;i<n;i++)
{
if(arr[i]==1)
{
count_1++;
arr[i]=-1;
}
else
arr[i]=1;
}
int max_sum=findmaxsum(arr);
max_sum=Math.max(0,max_sum);
return max_sum+count_1;
}
static int findmaxsum(int arr[])
{
int sum=0;
int max=Integer.MIN_VALUE;
for(int i:arr)
{
sum+=i;
if(sum>max)
max=sum;
if(sum<0)
sum=0;
}
return max;
}Interview problems
Easy and optimized C++ soln
#include <bits/stdc++.h>
int flipBits(int* arr, int n)
{
// WRITE YOUR CODE HERE
int cnt_one=0;
for(int i=0;i<n;i++)
{
if(arr[i]==0)
arr[i]=1;
else
{
arr[i]=-1;
cnt_one++;
}
}
int cursum=arr[0];
int maxsum=arr[0];
for(int i=1;i<n;i++)
{
cursum=max(arr[i],cursum+arr[i]);
maxsum=max(cursum,maxsum);
}
return max(maxsum,0)+cnt_one;
}
Interview problems
C++ Solution
#include <bits/stdc++.h>
using namespace std;
int flipBits(int *arr, int n) {
int countOnes = 0;
for (int i = 0; i < n; i++) {
if (arr[i] == 0)
arr[i] = 1;
else {
arr[i] = -1;
countOnes++;
}
}
int sum = 0, maxi = 0;
for (int i = 0; i < n; i++) {
sum += arr[i];
maxi = max(maxi, sum);
if (sum < 0)
sum = 0;
}
return countOnes + maxi;
}
import java.util.*;
import java.io.*;
public class Solution {
public static int flipBits(int[] arr, int n) {
int ones = 0, zeros = 0, maxZeros = 0;
for (int i = 0; i < n; i++) {
if (arr[i] == 1)
ones++;
if (zeros < 0)
zeros = 0;
if (arr[i] == 0)
zeros++;
else
zeros--;
maxZeros = Math.max(maxZeros, zeros);
}
return maxZeros + ones;
}
}
Interview problems
Flip bits
This is full optimized code I've implmented using only one for loop
The idea behind is,
I've maintained one count variable, which is initialized to zero.
Trying to find subarray where 0 is maximum.
in the array if one is encountered then decrement the count and if zero , then increment the count. From this we will get subarray which has max zeros
and finally return the number of 1's in the array plus max no of zeroes in the subarray.
int count=0;
int ponecount=0;
int maxcount=0;
for(int i=0;i<n;i++){
if(arr[i]){
count--;
ponecount++;
}
else
count++;
maxcount=max(maxcount,count);
if (count <= 0) {
count = 0;
}
}
return ponecount+maxcount;
