I was solving a problem and got stuck up. It states - We have a binary sequence of 0 and 1. We can perform this operation on the sequence any number of times : For any bit d which is 0, if there exists a 1(If there originally is a 1,and not after modification) on at least one of the previous two bits, i.e bits d−1 and d−2, and on at least one of the following two bits, i.e. bits d+1 and d+2, we can change it into a 1. However, it is impossible to modify the first two bits and the last two bits.
The weight of sequence is the total number of 1s in the sequence divided by length of sequence. We need to make this weight at least 0.75 and the goal is to find the minimum number of bits that need to be modified in order to make the weight of sequence at least 0.75 If we cannot make the weight at least 0.75 print -1
E.g.
Given sequence : 100110111
Answer = 1
Explanation : We can change bit 3 from 0 to 1, so the sequence becomes 101110111 whose weight is greater than 0.75
My approach :
I first found the initial weight of the sequence and if it was less than 0.75 then iterate through the sequence from bit position 2 to length-2, and for every bit having 0 check the condition for
[ {(d-1)=1 OR (d-2)=1} AND {(d+1)=1 OR (d+2)=1} ]
And recalculated the weight at every step and if the weight exceeds 0.75 then print the answer.
But this approach gives wrong answer.
