995. Minimum Number of K Consecutive Bit Flips

You are given a binary array nums and an integer k.

A k-bit flip is choosing a subarray of length k from nums and simultaneously changing every 0 in the subarray to 1, and every 1 in the subarray to 0.

Return the minimum number of k-bit flips required so that there is no 0 in the array. If it is not possible, return -1.

A subarray is a contiguous part of an array.

• Time : O(n)
• Space : O(n-k)

c++

class Solution {
    int fliped(vector<int>& dp, int i, int k) {
        if(i < k) return 0;
        return dp[i-k];
    }
public:
    int minKBitFlips(vector<int>& nums, int k) {
        int n = nums.size(), flip = 0;
        vector<int> dp(n - k + 1,0);
        for(int i = 0; i <= n - k; i++) {
            if(nums[i] == 0) {
                if((flip - fliped(dp,i,k)) & 1)  {
                    dp[i] = flip;
                } else dp[i] = ++flip;
            } else {
                if((flip - fliped(dp,i,k)) & 1)  {
                    dp[i] = ++flip;
                } else dp[i] = flip;
            }
        }
        for(int i = n - k + 1; i < n; i++) {
            if(nums[i] == 0) {
                if(!((flip - fliped(dp,i,k)) & 1)) return -1;
            } else {
                if((flip - fliped(dp,i,k)) & 1)  return -1;
            }
        }
        return flip;
    }
};