Algorithm (Greedy + Segment Tree)

We propose the following greedy algorithm:

1. Start scanning from left to right, if $A_{i}=0,$ we flip $A_{i:i+K-1}$ to $1$ and if $A_{i}=1$ we continue to $A_{i+1}.$
2. If $A_{i}=0$ and $A_{i:i+K-1}$ is not a valid sub-array, we return $-1$. Otherwise, we return the total number of flips performed.

Next, we prove that our algorithm is indeed correct. First, we fix some notations. Let $\mathrm{OPT}$ denote the set of optimal flips. Note that it is entirely possible that $\mathrm{OPT}$ contains more than one element.

Lemma 1. For any flipping sequence, the order of flipping is irrelevant.

Proof. Suppose we have a flipping sequence $\{f_{A_{n_{1}}},…,f_{A_{n_{k}}}\}$, where $n_{i}\in\{0,…,N-1\}.$ Then it could be understood as $$\mathrm{map}!(A_{n_{k}:n_{k}+K-1},\lambda x.x+1\ \mod2)\circ…\circ\mathrm{map}!(A_{n_{1}:n_{1}+K-1},\lambda x.x+1\ \mod2),\label{eq:995-1}\tag{1}$$ where $\mathrm{map}!$ is the in-place version of the $\mathrm{map}$ function. Since modular addition is commutative, the order in which we apply each $\mathrm{map}!$ then becomes irrelevant.

Lemma 2. For any optimal sequence $S\in\mathrm{OPT},$ if $S$ involves flipping $A_{j}$ for some $j\in\{0,…,N-1\}$, it only does the flip once.

Proof. We prove the claim by contradiction. Suppose on the other hand that there exists $S_{0}\in\mathrm{OPT}$ such that $S_{0}$ flips the $K$-sub-array starting from $A_{j}$ $t$ times, where $t>1$. Since the flipping is order invariant, if $t$ is odd, it is equivalent to an alternative $S_{0}’$ which flips $A_{j}$ just once; if $t$ is even, it is then equivalent to an alternative $S_{0}^{\dagger}$ which doesn’t flip $A_{j}$ at all. Since both $S_{0}^{\dagger}$ and $S_{0}’$ are strictly better flip sequences (in terms of number of flips), it follows that $S_{0}\notin\mathrm{OPT}$ which a contradiction. Hence, the result follows.

Lemma 3. Our algorithm produces an element in $\mathrm{OPT}$.

Proof. Let $\mathrm{ALT}$ denote any successful flipping sequences generated in ways that are different from our algorithm. To prove this, we need to show that any element in $\mathrm{ALT}$ is no better than ours. The element in $\mathrm{ALT}$ varies drastically; so the only sensible way to go forward is to do an exhaustive case analysis. Let $\mathrm{FLIP}_{\alpha}\in\mathrm{ALT}$. Then we have the following possible cases:

Case: $\mathrm{FLIP}_{\alpha}$ also scans from left to right, but flips at least one $1$. Let $j$ be the smallest index such that $A_{j}=1$ and $A_{j}$ was flipped. We claim that $A_{0:j-1}$ is all $1$. This is because we are scanning from left to right, if there is a 0 among $A_{0:j-1}$ and we didn’t flip it, the final resulting sequence will contain that $0$, thus rendering $\mathrm{FLIP}_{\alpha}$ invalid.

• First, we assume that the flip on $A_{j}$ flips some $A_{k}=0$ to $A_{k}=1$ for some $k\in[j,…,j+K-1].$ Note that by construct we have that after the flip, $A_{j:k-1}=[0,…,0].$ We claim that the only way to get a successful flip in the end is to flip $A_{j}$ again. Suppose our claim is not true. Then there exists some $A_{l}$ for some $\in[k-K,j-1]$ that were flipped to make $A_{j:k-1}$ back to $1$. However, this is contradiction because we have already scanned all $A_{i}$ for $i\in[0,…,j-1]$ and made the decision to flip or not. So we ended up flipping $A_{j}$ twice, which is equivalent to not touching it at all. Therefore, in this case $\mathrm{FLIP}_{\alpha}$ is suboptimal.

• The similar reasoning could be extended to the case where $A_{j:j+K-1}=[1,…,1].$

Case: $\mathrm{FLIP}_{\alpha}$ does not scan from left to right. This case can be reduced to the first case because of order invariance.

Since we have proved the algorithm is correct, we need to come up with an efficient implementation as the native implementation is $O(nK)$. The range update operation, once written in the form in \eqref{eq:995-1} could be implemented using a homogeneous lazy segment tree. And the rest is just formality.

There is a $O(n)$ algorithm. But we skip it because I think it is not natural and hard to come up in first try.

Code (Cpp17)

template <class T, T mod>
struct modular_plus_monoid {
  typedef T value_type;
  value_type unit() const { return value_type{}; }
  value_type mult(value_type a, value_type b) const { return (a + b) % mod; }
};

template <class Monoid>
class homogeneous_lazy_segment_tree {
 private:
  typedef typename Monoid::value_type value_type;
  static constexpr auto mon = Monoid{};

 private:
  mutable std::size_t n_;
  mutable std::vector<value_type> f_;

 public:
  homogeneous_lazy_segment_tree() = default;
  homogeneous_lazy_segment_tree(std::size_t n) { resize(n); }

  template <class InputIterator>
  homogeneous_lazy_segment_tree(InputIterator first, InputIterator last) {
    resize(std::distance(first, last));
    std::copy(first, last, f_.begin() + (n_ - 1));
  }

  void resize(std::size_t n, std::optional<value_type> value = {}) {
    n_ = 1 << (32 - __builtin_clz(n));
    f_.resize(2 * n_ - 1, mon.unit());
    if (value)
      range_apply(0, n_, *value);
  }

  value_type fast_point_get(int i) const { 
    value_type acc = mon.unit();
    for (i += n_; i > 0; i /= 2) 
      acc = mon.mult(f_[i - 1], acc);
    return acc;
  }

  value_type point_get(int i) const { return range_get(0, 0, n_, i, i + 1); }
  void point_apply(int i, value_type g) { range_apply(i, i + 1, g); }
  void range_apply(int l, int r, value_type g) { range_apply(0, 0, n_, l, r, g); }

 private:
  value_type range_get(int i, int il, int ir, int l, int r) const {
    if (l <= il and ir <= r)
      return f_[i];
    else if (ir <= l or il >= r)
      return mon.unit();
    else {
      const auto lacc = range_get(2 * i + 1, il, (il + ir) / 2, l, r);
      const auto racc = range_get(2 * i + 2, (il + ir) / 2, ir, l, r);
      return mon.mult(f_[i], mon.mult(lacc, racc));
    }
  }

  void range_apply(int i, int il, int ir, int l, int r, value_type g) {
    if (l <= il and ir <= r) {  // 0-based
      f_[i] = mon.mult(g, f_[i]);
    } else if (ir <= l or r <= il) {
      // nop
    } else {
      range_apply(2 * i + 1, il, (il + ir) / 2, 0, n_, f_[i]);
      range_apply(2 * i + 2, (il + ir) / 2, ir, 0, n_, f_[i]);
      f_[i] = mon.unit();
      range_apply(2 * i + 1, il, (il + ir) / 2, l, r, g);
      range_apply(2 * i + 2, (il + ir) / 2, ir, l, r, g);
    }
  }

};

class Solution {
 public:
  int minKBitFlips(vector<int>& A, int K) {
    const auto n = size(A);
    auto RUQ = homogeneous_lazy_segment_tree<modular_plus_monoid<char, 2>>(std::begin(A), std::end(A));
    const auto solution = [&](int acc = 0) {
      for (int i = 0; i < n and acc != -1; ++i) {
        const auto A_i = RUQ.point_get(i);
        if (A_i == 0 and i + K - 1 >= n)
           acc = -1;
        else if (A_i == 0 and i + K - 1 <= n - 1)
          ++acc, RUQ.range_apply(i, i + K, 1);
      }
      return acc;
    }();
    return solution;
  }
};