Flip Bits
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.

Input format :

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.

Output format :

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.

Note:

You don’t have to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1

Question

Flip Bits

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.

Input format :

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.

Output format :

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.

Note:

You don’t have to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1 <= T = 100
1 <= N <= 10^4
0 <= ARR[i] <= 1

Time Limit: 1 sec

Accepted Answer

Property of XOR can be used to solve this problem. 1^0 = 1 and 1^1 = 0
First, we calculate the number of digits in the given number using log.
Next, generate a number with digits equal to the digits in the given number and all bits set to 1.
The last step is to take the xor of the given number with the generated number.
The time complexity of this solution is O(log n).

Accepted Answer

Brute force

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.

Initialize TOTALONES to zero, which will store the total count of ones in the array.
Now by running two nested loops outer one starting from index I= 0 and the inner one starting from index I, and both running till the end of the array.
Inside the loop: if you encounter one, update TOTALONES by incrementing one to it.
Initialize COUNT1 and COUNT0 to zero, which will store the count of 1 and 0, respectively.
Consider all subarrays starting from I and find the difference between 1s and 0s.
Update MAX on every iteration to store the answer.
Finally, return the count of all the ones in the array by the sum TOTALONES + MAX.

Space Complexity: O(1)Explanation:

O(1)

We are using constant space.

Time Complexity: O(n^2)Explanation:

O(N ^ 2), Where ‘N’ denotes the number of elements in the Array

Since we are using two nested loops.

Accepted Answer

Kadane's algorithm

This problem can be interpreted as a version of Kadane's algorithm.

Actually, we want to consider a subarray that maximizes the difference between the count of ones and zeroes. If we change 1s to -1 and change 0 to 1, then the sum of values will give us the maximum difference between the counts(MAX). So, we have to find a subarray with the maximum sum, which can be done by Kadane’s Algorithm. Finally, we return the MAX plus count of ones in the original array.

Initialize MAX and CURRMAX to zero; these variables store overall max diff for any subarray and the current difference in the subarray respectively.
Initialize TOTALONES to zero, which will store the total count of ones in the array.
Now by running a loop from index I=0 check, Inside the loop: if you encounter one, update TOTALONES by incrementing one to it.
And consider value if 1 as -1 and 0 ans as 1 i.e. VAL = (ARR[i] == 1)? -1 : 1;
Initialize COUNT1 and COUNT0 to zero, which will store the count of 1 and 0, respectively.
Update CURRMAX and MAX i.e. CURRMAX = Math.max(VAL, CURRMAX + VAL); and MAX = Math.max(MAX, CURRMAX);
Finally, return the count of all the ones in the array by returning the TOTALONES + MAX.

Space Complexity: O(1)Explanation:

O(1)

We are using constant space.

Time Complexity: O(n)Explanation:

O(N), Where ‘N’ denotes the number of elements in the Array

Since we are traversing the array once.