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??
u need to minimize the number of operations ??
yes
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.
Is it a codeforces problem that I can submit it in problemset ?? sorry for my bad english
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.
What you've asked is a simpler version of the attached problem.Link