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??
Auto comment: topic has been updated by ankushmondal1y2t (previous revision, new revision, compare).
u need to minimize the number of operations ??
yes
Auto comment: topic has been updated by ankushmondal1y2t (previous revision, new revision, compare).
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.
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,
if((total_bits-cnt)%4==0 || (total_bits+cnt)%4==0){ cout<<cnt<<endl;}; else{cout<<cnt+2<<endl;}
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
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
its an advanced version