Make maximum 1's by flipping k bits at a time

user_9172533 0
Viewed 344

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):

  • Choose exactly k bits(not necessarily continuous) and flip their state (0 to 1, 1 to 0);

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.

  • xxxx_
  • xxx_x

'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.

bitstring mathematical-optimization bit algorithm
2 Answers

Flip zeroes until the number of zeroes is below k. Let m be the number of zeroes.

Flip k - m/2 ones and m/2 zeroes (integer division). Now you have m + (k-m/2) - m/2 = m + k - m/2 - m/2 ~ k zeroes. (approximate b/c of the integer division).

Finally, flip all the zeroes and as many ones as necessary to get k total flips. This will be either all ones or close depending on the parity of m.

user_20410770

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.

user_91725330
Related