The necessary and sufficient condition for the second player to win is that the lengths of all maximal intervals of consecutive \(1\)s are \(2\) (or all elements are \(0\)).

Indeed, this can be shown by induction using the following facts.

• When the lengths of all maximal intervals of consecutive \(1\)s are \(2\):
  • No matter how the operation is performed, there will be some interval whose length is not \(2\).
• When there is a maximal interval of consecutive \(1\)s whose length is not \(2\):
  • For an interval of length \(1\), it can be turned to \(0\) and removed.
  • For an interval of length \(3\) or more, it can be split into multiple intervals of length \(2\) by choosing appropriately.
    Example for length \(4\): \((1,1,1,1) \rightarrow (0,1,1,0)\)
    Example for length \(5\): \((1,1,1,1,1) \rightarrow (1,1,0,1,1)\)
  • When there are multiple such maximal intervals, the operation can be simultaneously performed on them independently, so the lengths of all maximal intervals can be made \(2\) (or all elements can be made \(0\)).

The winner can be determined in \(O(N)\).