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

**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 [].
```

/** * @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[0] = res[1] = -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[0] = start; res[1] = end = i; } } if (res[0] != -1 && res[1] != -1) { res[0] = res[0] + 1; res[1] = res[1] + 1; *len1 = 2; } return res; }

comments powered by Disqus