When \(N = 1\), the answer is \(\lbrace 1 \rbrace\). Below, assume \(N \ge 2\).

If we put \(1\) into \(S\), then for every \(k \ge 2\) we have \(1 \bmod k = 1\), which prevents us from putting any other element into \(S\). Moreover, there are other good sets of size \(1\). Therefore, we may assume that \(1\) is not included in \(S\).

Because for every \(k \ge 2\) we have \((k+1) \bmod k = 1\), two consecutive integers cannot both belong to \(S\). To satisfy this restriction we need \(|S| \le \lfloor \tfrac{N}{2} \rfloor\). If we take \(S\) to be the set of all even integers between \(1\) and \(N\), then \(|S| = \lfloor \tfrac{N}{2} \rfloor\) and \(S\) is a good set. This gives one construction.

Bonus: Pushing the above discussion further shows that for \(N \ge 6\) the above construction is the only answer, so the judge can operate in \(\mathrm{O}(N)\) time.