Given an n-bit vector and an integer k, 1 <= k <= n, we have to maximize the number of ones in it by applying the following operation any number of times(including zero):
After some analysis, I have come to the conclusion if n > k, we can also flip any two bits simultaneously. For example for n = 5, k = 4. We can do something like this to flip last two bits only.
'x' represents that we flip the bit at that position.
But I am not sure how to proceed after that and I am unable to make any more observations. So, what would be a correct approach? You may assume an n^2 algorithm is feasible.
Dave's approach seems correct. I will share mine that I figured out after I posted the question here.
Let the number of zeroes be z, now convince yourself that if k < n, we can flip any two bits(a pair) by using a combination of the k-bit operation mentioned in the problem. Here's an argument to help you satisfy yourself with this fact, choose any k - 1 bits other than the pair you want to flip; then choose one bit from the pair along with the k - 1 we just picked, apply the operation; then choose the other bit from the pair along with the same k - 1 bits we picked earlier, apply the operation again. We are guaranteed to find these k - 1 auxiliary bits if k < n or n is at least k + 1.
So naturally, two cases arise:
k == n : clearly we can only flip all or flip none. So the answer is max(n - z, z)k < n : In this case, we can flip any k bits or we can flip any 2 bits(using the argument above). Now, if z < k, we can only use the 2-bit flips and if z is odd, we are left with one bit still 0, answer is n - 1; if z is even, we flip all of them to 1's, so answer is n. Now when z >= k, we can use both k-bit fips and 2-bit flips, the claim is, if z is odd and k is even, we are left with one 0(answer is n - 1) otherwise we can always turn all 0's to 1's(answer is n). Explanation of the last claim: If we can use both k-bit flips and 2-bit flips and z happens to be odd, we try to use one k-bit flip to change the parity of remaining 0's(parity of z - k). We can only do so if k is odd otherwise we can't do it and using 2-bit operations on odd number of zeroes will leave us with one zero. So, in a nutshell, if k is even with odd z, we will be left with one 0, otherwise we get all 1's.