# Arrays - Flip elements in array to get maximum 1s

2 users say they have been asked this quesiton in interview.
Difficulty Level:

### Problem Statement:

You are given a binary string(i.e. with characters `0` and `1`) S consisting of characters S1, S2, …, SN. In a single operation, you can choose two indices L and R such that 1 ≤ L ≤ R ≤ N and flip the characters SL, SL+1, …, SR. By flipping, we mean change character `0` to `1` and vice-versa.

Your aim is to perform ATMOST one operation such that in final string number of `1s` is maximised. If you don’t want to perform the operation, return an empty array. Else, return an array consisting of two elements denoting L and R. If there are multiple solutions, return the lexicographically smallest pair of L and R.

Notes: `Pair (a, b) is lexicographically smaller than pair (c, d) if a < c or, if a == c and b < d`

For example,

```  ```S = 010

Pair of [L, R] | Final string
_______________|_____________
[1 1]          | 110
[1 2]          | 100
[1 3]          | 101
[2 2]          | 000
[2 3]          | 001

We see that two pairs [1, 1] and [1, 3] give same number of 1s in final string. So, we return [1, 1].
``````

Another example,

```  ```If S = 111

No operation can give us more than three 1s in final string. So, we return empty array [].``````
Solution:
```/**
* @input A : String termination by '\0'
*
* @Output Integer array. You need to malloc memory, and fill the length in len1
*/
int* flip(char* A, int *len1) {
int i,j;
int len = strlen(A);
int finalsum = 0;
int sum = 0;
int *res = (int*)malloc(sizeof(int)*2);
int start, end;
*len1 = 0;
res = res = -1;
start = end = 0;

for (i = 0; i < len; i++) {
if (A[i] == '0')
sum += 1;
else
sum -= 1;

if (sum < 0) {
sum = 0;
start = i+1;
}

if (sum > finalsum) {
finalsum = sum;
res = start;
res = end = i;
}
}

if (res != -1 && res != -1) {
res = res + 1;
res = res + 1;
*len1 = 2;
}

return res;
}
```
comments powered by Disqus