Arrays - Flip elements in array to get maximum 1s
Problem Statement:
You are given a binary string(i.e. with characters0
and1
) 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 character0
to1
and vice-versa.
Your aim is to perform ATMOST one operation such that in final string number of1s
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