LeetCode #995 Minimum Number of

QQ20210408-124020.png

I first tried to solve this problem brute-forcely, but exceeded time limit; here's the code:

int minKBitFlips(int* a, int n, int k){
    int flips = 0, step; 
    for (int i = 0; i < n - k; i += step) {
        int *startptr = a + i;
        step = 0;
        if (*startptr == 0) {
            flips++;
            int *ptr = startptr;
            int *hiptr = ptr + k;
            while (*ptr == 0 && ptr < hiptr) {
                *ptr = 1;
                ptr++;
                step++;
            }
            
            while (ptr < hiptr) {
                *ptr ^= 1;
                ptr++;
            }
        } else {
            int *ptr = startptr;
            int *hiptr = ptr + k;
            while (*ptr == 1 && ptr < hiptr) {
                ptr++;
                step++;
            }
        }
    }
    int sum = 0;
    int *ptr = a + (n - k);
    int *hiptr = a + n - 1;
    while (ptr < hiptr) {
        sum += *ptr;
        ptr++;
    }
    if (sum == 0) { flips += 1; }
    return (sum == 0 || sum == k) ? flips : -1;
}

the code here giving the correct result(not in time, though) means that the idea behind it works;
only the implementation need some abstraction to speed things up; the problem with this implementation
is that it repeatedly flips the bits in the array, from 0 to 1, then back to zero; with tens of thousands
of bits to flip this way, too much time will be spent. We need to reduce the number of bits
we need to flip; here's how:
we 'fold'(or 'compress') consecutive bits into a single bit and store the numbers of bits into another array. An
example helps illustrate how this idea works:
the sequence
[0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0]
will be 'folded' into:
bits: [1, 0, 1]
nums: [5, 3, 3]//five 0s, three 1s and three 0s
this way, we reduce the number of flips from 5 + 3 + 3 = 11 to 3
here's the code that implements this idea:

int minKBitFlips(int* a, int n, int k) {
    int bits[n], nums[n], head = 0, tail = 0, flips = 0;
    bits[head] = a[0];
    nums[head] = 0;
    int i = 0;
    while (i < k) {
        if (*(a + i) == *(bits + head)) {
            (*(nums + head))++;
        } else {
            head++;
                *(nums + head) = 1;
                *(bits + head) = *(a + i);
        }
        i++;
    }
    if (i == n) { return tail == head ? (a[0] == 0 ? 1 : 0) : -1; }

    do {
        if (*(bits + tail) == 0) {
            flips++;
            for (int j = tail; j <= head; j++) {
                *(bits + j) ^= 1;
            }            
        }
        
        int front = i + *(nums + (tail++));
        if (front > n) { front = n; }
        if (tail > head) {
            tail = head = 0;
            *(nums + head) = 0;
            *(bits + head) = *(a + i);
        }
        while (i < front) {
            if (*(a + i) == *(bits + head)) {
                (*(nums + head))++;
            } else {
                head++;
                *(nums + head) = 1;
                *(bits + head) = *(a + i);
            }
            i++;
        }
    } while (i < n);

    
    return (tail == head) ? (nums[tail] == k ? (flips + (bits[tail] == 0 ? 1 : 0)) : (bits[tail] == 1 ? flips : -1)) : -1;
}

Anyway the description of this problem immediately indicates that it's actually a dp problem(so I'll write a dp solution later).