_995. Minimum Number of K Consecutive Bit Flips.md

995. Minimum Number of K Consecutive Bit Flips

Back to top

---

First completed : June 23, 2024

Last updated : June 23, 2024

---

Related Topics : Array, Bit Manipulation, Queue, Sliding Window, Prefix Sum

Acceptance Rate : 51.646 %

---

To see the question prompt, click the title.

Solutions

• h995 Daily.c
• h995.py

C

h995 Daily.c

int minKBitFlips(int* nums, int numsSize, int k) {
    int flips = 0;
    int windowFlips = 0;
    int hmap[] = {1, 0};

    bool flipped[numsSize];
    memset(flipped, 0, sizeof(bool) * numsSize);

    for (int i = 0; i < numsSize; i++) {
        if (i >= k && flipped[i - k]) {
            windowFlips--;
        }

        int current = nums[i];

        if (windowFlips % 2) {
            current = hmap[current];
        }

        if (!current) {
            if (i + k > numsSize) {
                return -1;
            }

            windowFlips++;
            flips++;
            flipped[i] = true;
        }
    }
    return flips;
}

Python

h995.py

class Solution:
    def minKBitFlips(self, nums: List[int], k: int) -> int:
        flips = 0
        numsFlipped = [False] * len(nums)
        flippedInWindow = 0

        hmap = (1, 0)

        for i, num in enumerate(nums) :
            if i >= k and numsFlipped[i - k] :
                flippedInWindow -= 1

            # odd number of flips
            if flippedInWindow % 2 :
                num = hmap[num]

            # is zero
            if not num :
                if i + k > len(nums) :
                    print(flips)
                    return -1
                
                flippedInWindow += 1
                flips += 1
                numsFlipped[i] = True

        return flips