ankushmondal1y2t's blog

I can't solve this ploblem !!!
By ankushmondal1y2t, history, 3 months ago, In English

You are given a binary string and you have to find out minimum bits to flip(either from 0 --> 1 or 1 --> 0) to become number of 1's divisible by 4 and palindrome string

example s = 1110 if i flip the last bit 0 to 1 then the string becomes 1111 which is palindrome and the number of 1's divisible by 4

in one operation u can do flip 1 to 0 then 0 to 1 you have to just find out the minimum bits to flip to satisfy the following condition

can anyone tell me its solution or intuition??

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ankushmondal1y2t (previous revision, new revision, compare).

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

u need to minimize the number of operations ??

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ankushmondal1y2t (previous revision, new revision, compare).

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

First we must flip either s[i] or s[n — i + 1] if s[i] != s[n — i + 1]. So let's count number of such i, let it be cnt. Also let number of 1 in s be k. If cnt % 2 = k % 2 and cnt >= min(k % 4, 4 — k % 4) that means answer is cnt. If cnt % 2 != k % 2 that means we have 1 in the middle so we must flip it. Otherwise we can increase cnt using greedy approach.

→ Reply
»
3 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

first count the number of 1 bits in total_cnt, first start from mid, and expanding outwards(using i, n-1-i), and if bits are different, increase the count, after this iteration, you will get number of bit that u necessarily need to flip to keep the condition of palindrome. now u can turn the cnt bits either to 0 or 1, as both will make the condition of palindrome, so you check,

pseudo

Edit: for odd sized array, as middle element make no difference in divisible by 4, so we consider from mid-1,mid+1, and decrease the total_bits by 1 if mid was 1 bit, rest all is same. i think this is correct in my opinion

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it a codeforces problem that I can submit it in problemset ?? sorry for my bad english

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    There's a binary grid variation of this problem that came up in a Leetcode contest few days ago. You may try solving and submitting there. Here's the Link for your convenience.

    → Reply
»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

What you've asked is a simpler version of the attached problem.Link

→ Reply