5

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.

Manish Chandra Joshi
  • 431
  • 2
  • 11
  • If *n-k* is small the naive O(n^k) approach could be fast enough, – MrSmith42 Jun 13 '19 at 11:48
  • @MrSmith42 Sadly, n - k isn't guaranteed to be small enough. Nonetheless, can you share the naive solution? I am unable to imagine any brute-force. – Manish Chandra Joshi Jun 13 '19 at 11:54
  • 3
    [This question](https://math.stackexchange.com/questions/1476533/n-bits-flip-exactly-m-bits-at-a-time-what-is-minimum-number-of-operations-to-g) should give you a good start. –  Jun 13 '19 at 12:22

2 Answers2

2

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.

Dave
  • 7,460
  • 3
  • 26
  • 39
1

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.

Manish Chandra Joshi
  • 431
  • 2
  • 11