You are given a strings of 0 and 1's. Now the task is to make the string consisting of only 1's. But you are allowed to perform only the following operation:
Take exactly k consecutive elements of string and change 1 to 0 and 0 to 1. Each operation takes 1 unit time so you have to determine the minimum time required to make the string of 1's only. If not possible return -1.
2 ≤ length of S ≤ 1000
Examples
Input
S = 00010110 k = 3
Output
3
Explanation
You can get 1 by first changing the leftmost 3 elements, getting to 11110110, then the rightmost 3, getting to 11110001, and finally the 3 left out 0's to 11111111; In 3 unit time.
Any approaches for it.
Yeah, it works. it cant be anything else than a minimum number. We can only just invert k symbols. It is true answer.
This is a problem from Google Code Jam's 2017 Qualification round. Here's the link to the editorial: https://code.google.com/codejam/contest/3264486/dashboard#s=a&a=0