0
Suppose I have a binary vector a = (0,1,1,1,0,0) of length $N$. I want to detect in a linear way whether a has any gaps in consecutive 1's. a as defined above has no gaps. But b = (0,1,0,1,0,0) has gaps.
Quadratic solution:
$$\sum_i^N a_i - \sum_i^{N-1}a_i a_{i+1} \le 1$$
Linear solution:
$$?$$...