Social Experiment

Each team has size $2$ or $3$, and a whole team chooses exactly one civilization. So we are not splitting people freely; each civilization gets a sum of team sizes.

The key observation is simple:

A nonnegative integer $s$ can be formed as a sum of $2$'s and $3$'s iff $s \ne 1$.

Why?

• $0$ is possible by giving that civilization no teams.
• $2$ and $3$ are directly possible.
• Every $s \ge 4$ is possible: if $s$ is even, use $s/2$ teams of size $2$; if $s$ is odd, use one team of size $3$ and fill the rest with teams of size $2$.
• $1$ is impossible, because teams cannot have size $1$.

Now suppose one civilization gets $x$ people. The other gets $n-x$ people. We need both $x$ and $n-x$ to be valid side populations, meaning neither can equal $1$. The difference is

$$|x-(n-x)| = |2x-n|.$$

To minimize this, we want $x$ as close to $n/2$ as possible.

If $n$ is even and $n \ge 4$, take

$$x = \frac n2.$$

Then both civilizations get $n/2 \ge 2$ people, so both are valid, and the answer is $0$.

If $n$ is odd and $n \ge 5$, take

$$x = \frac{n-1}{2}, \qquad n-x = \frac{n+1}{2}.$$

Both values are at least $2$, so both are valid. Their difference is $1$, and no odd total can be split with difference $0$, so the answer is $1$.

Now for the annoying tiny cases, because of course they exist:

• $n=2$: only one team of size $2$ can be formed. It must choose one civilization, leaving the other with $0$. Difference is $2$.
• $n=3$: only one team of size $3$ can be formed. Difference is $3$.

So the final formula is:

$$\text{ans} = \begin{cases} 2, & n=2,\\ 3, & n=3,\\ n \bmod 2, & n \ge 4. \end{cases}$$

The common wrong assumption is "just balance people individually." Nope. Teams are indivisible, and a civilization cannot receive exactly one person. That's the whole problem hiding under the couch.

Complexity per test case is $O(1)$, with $O(1)$ memory.