995. Minimum Number of K Consecutive Bit Flips LeetCode Solution

In this guide, you will get 995. Minimum Number of K Consecutive Bit Flips LeetCode Solution with the best time and space complexity. The solution to Minimum Number of K Consecutive Bit Flips problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Minimum Number of K Consecutive Bit Flips solution in C++
4. Minimum Number of K Consecutive Bit Flips solution in Java
5. Minimum Number of K Consecutive Bit Flips solution in Python
6. Additional Resources

Problem Statement of 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.

Example 1:

Input: nums = [0,1,0], k = 1
Output: 2
Explanation: Flip nums[0], then flip nums[2].

Example 2:

Input: nums = [1,1,0], k = 2
Output: -1
Explanation: No matter how we flip subarrays of size 2, we cannot make the array become [1,1,1].

Example 3:

Input: nums = [0,0,0,1,0,1,1,0], k = 3
Output: 3
Explanation:
Flip nums[0],nums[1],nums[2]: nums becomes [1,1,1,1,0,1,1,0]
Flip nums[4],nums[5],nums[6]: nums becomes [1,1,1,1,1,0,0,0]
Flip nums[5],nums[6],nums[7]: nums becomes [1,1,1,1,1,1,1,1]

Constraints:

1 <= nums.length <= 105
1 <= k <= nums.length

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

995. Minimum Number of K Consecutive Bit Flips LeetCode Solution in C++

class Solution {
 public:
  int minKBitFlips(vector<int>& nums, int k) {
    int ans = 0;
    int flippedTime = 0;

    for (int i = 0; i < nums.size(); ++i) {
      if (i >= k && nums[i - k] == 2)
        --flippedTime;
      if (flippedTime % 2 == nums[i]) {
        if (i + k > nums.size())
          return -1;
        ++ans;
        ++flippedTime;
        nums[i] = 2;
      }
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

995. Minimum Number of K Consecutive Bit Flips LeetCode Solution in Java

class Solution {
  public int minKBitFlips(int[] nums, int k) {
    int ans = 0;
    int flippedTime = 0;

    for (int i = 0; i < nums.length; ++i) {
      if (i >= k && nums[i - k] == 2)
        --flippedTime;
      if (flippedTime % 2 == nums[i]) {
        if (i + k > nums.length)
          return -1;
        ++ans;
        ++flippedTime;
        nums[i] = 2;
      }
    }

    return ans;
  }
}
// code provided by PROGIEZ

995. Minimum Number of K Consecutive Bit Flips LeetCode Solution in Python

class Solution:
  def minKBitFlips(self, nums: list[int], k: int) -> int:
    ans = 0
    flippedTime = 0

    for i, num in enumerate(nums):
      if i >= k and nums[i - k] == 2:
        flippedTime -= 1
      if flippedTime % 2 == num:
        if i + k > len(nums):
          return -1
        ans += 1
        flippedTime += 1
        nums[i] = 2

    return ans
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.