The minimum number of operations is always at most \(2\). We handle the cases of \(0,1,2\) operations separately.

The case with zero operations is trivial.

Consider the condition for being sortable in one operation. Let \(L\) be the minimum \(i\) satisfying \(X_i=0\). Let \(R\) be the maximum \(i\) satisfying \(X_i=1\). If \(L>R\), \(X\) has the form \(X=(1,\cdots,1,0,\cdots,0)\), so we reverse the entire sequence.

Consider when \(L<R\). Without loss of generality, assume that \(X_L\) is placed in group A. If we place a \(1\) to the right of \(L\) in group A, \(X\) will not be sorted after the operation, so all \(1\)s to the right of \(L\) must be placed in group B. In particular, \(X_R\) is placed in group B, and by similar reasoning, all \(0\)s to the left of \(R\) must be placed in group A.

Therefore, the grouping of \(X_L,\cdots,X_R\) is determined. Here, let \(C\) be the number of \(0\)s contained in \(X\). Let \(D\) be the number of \(i\) satisfying \(C<i<R\) and \(X_i=0\). These \(D\) positions are placed in group A, but after the operation, these positions should be swapped with \(i\) satisfying \(i<L,\ i \leq C\). From this, we derive the condition \(\min(L-1,C)\geq D\).

Actually, this is a sufficient condition for \(X\) to be sortable in one operation. Indeed, by assigning \(\{1,\cdots,D\}\) and “all \(i\) satisfying \(L \leq i \leq R,\ X_i=0\)” to group A, and assigning everything else to group B, we can sort \(X\).

We now know the condition for \(X\) to be sortable in one operation. Finally, we show that any \(X\) can be sorted in two operations.

Continuing from before, let \(C\) be the number of \(0\)s. Without loss of generality, assume \(C \geq N-C\). Let \(P\) be the number of \(0\)s contained in the first \(N-C\) terms of \(X\). We assign these \(P\) elements and the last \(P\) elements of \(X\) to group A, and assign everything else to group B.

After performing one operation with this grouping, the last \(N-C\) terms of \(X\) have the form \(1,\cdots,1,0,\cdots,0\). At this point, we can verify that the condition for sorting \(X\) in one operation is satisfied.

Therefore, we have proved that any \(X\) can be sorted in at most two operations. By directly implementing the procedure shown in the proof, we get a solution with time complexity \(O(N)\).

Sample solution (C++)