package question;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author Roderland
 * @since 1.0
 */
public class Question995 {
 public int minKBitFlips(int[] A, int K) {
 int[] arr = new int[A.length+1];
 int res=0;
 int cnt=0;
 for (int i=0; i<A.length; i++) {
 cnt+=arr[i];
 if (((A[i]+cnt)&1)==0) {
 if (i+K>=arr.length) return -1;
 arr[i+1]++;
 arr[i+K]--;
 res++;
 }
 }
 return res;
 }

 public int minKBitFlips2(int[] A, int K) {
 int res=0;
 Queue<Integer> queue = new LinkedList<>();
 for (int i=0; i<A.length; i++) {
 if (!queue.isEmpty() && i-queue.peek()>=K) queue.poll();
 if (((queue.size()+A[i])&1)==0) {
 if (i+K>A.length) return -1;
 queue.add(i);
 res++;
 }
 }
 return res;
 }
}