Flipping Coins

Moderate

0/80

Average time to solve is 32m

13 upvotes

Asked in companies

Problem statement

Gary has N coins placed in a straight line. Some coins have head side up, and others have the tail side up.

Convention:

1 denotes the HEAD side is up. 
0 denotes the TAIL side is up.

Now, Gary wants to obtain a maximum number of head-side up coins. He can perform at most one(possibly 0) flip in which he can flip the coins of a continuous interval (continuous subarray).

For example: In the given array (0 based indexing), { 1, 0, 0, 1, 0, 0, 1 }, we can obtain maximum head side up coins by flipping the coins in range 1 to 5. The array will thus become {1, 1, 1, 0, 1, 1, 1 }.

Return the maximum number of heads side up Gary can obtain.

Detailed explanation ( Input/output format, Notes, Images )

Input format:

The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then, the test cases follow.

The first line of each test case or query contains an integer 'N' representing the number of coins.

The second line contains 'N' single space-separated integers (0 or 1) representing the upside of the coins.

Output format:

For each test case, print the count of maximum head side up coins that can be obtained in a single line.

Output for each test case will be printed in a separate line.

Note

You are not required to print anything, and it has already been taken care of. Just implement the function.

Constraints:

1 <= T <=10     
1 <= N <= 10^5 
0 <= arr[i] <= 1

where 'T' is the number of test cases, 'N' is the total number of coins, and 'arr[i]' denotes whether the coin is head side up or tail side up.
Time limit: 1 sec.

Sample input 1:

1
4
1 0 1 0

Sample output 1:

Explanation

{ 1, 1, 1, 0} is one possible answer if we flip range 1-1.

Sample input 2:

Sample output 2:

4
3

Hint 1

Hint 2

First off, observe that the question focuses on the keyword ‘subarray’. Thus, all we need to do is work on every subarray one by one.

Approaches (2)

Approach 1

Approach 2

Brute force

The idea is to check every subarray.
We can count the number of heads and number tails in every subarray and then calculate the maximum number of heads side up we can obtain if we flip that particular subarray.
We also keep a count of the final start index and final end index that will give us the number of heads side up we can obtain later.

Time Complexity

O(N^2) per test case, where N is the number of coins.

In the worst case, we will be traversing all the possible subarrays. Thus, we will need 2 nested loops for start and end. Hence, O(N^2).

Space Complexity

O(1).

In the worst case, only a constant extra space is required.

(100% EXP penalty)

Flipping Coins

Console