Using the numbers ~1, 2, 3, \dots, k~, we can make the numbers ~1, 2, 3, \dots, 2k-1~. For the remainder of this editorial, let ~[a, b]~ represent the list of numbers from ~a~ to ~b~ (inclusive).

Instead of using ~[1, k]~, what happens when we have ~[2, k+1]~, ~[3, k+2]~, etc.?

Suppose we have the numbers ~[k, 2k-1]~. We can make the numbers ~[1, k-1]~ and ~[2k+1, 4k-3]~ but we cannot make the numbers ~[k, 2k]~. This is because the largest possible difference is ~k-1~ and the smallest possible sum is ~2k+1~. We can fill in this gap by extending the array to ~[k, 3k]~, which now covers the numbers ~[1, 6k-1]~.

Expressing in terms of ~N~, we have an optimal value of ~k = \left\lceil\dfrac{N+1}{6}\right\rceil~. This results in a length of ~2k+1 = 2\left\lceil\dfrac{N+1}{6}\right\rceil+1~, which approaches ~\dfrac{1}{3}N~ for large values of ~N~. To satisfy the length requirement for smaller values of ~N~, we can remove the middle two array elements while still being able to construct all the numbers. This works for ~k \ge 4~, which is always true for ~N \ge 18~.

~\mathcal{O}(N)~

What could the square root in ~\sqrt{2N}~ imply? Also think about multiples.

Let's reconsider the numbers ~[1, k]~. Notice that if we have some other number ~p~, we can make the numbers ~[p-k, p+k]~ except for ~p~ itself. Thus, we can try adding numbers so that the range of numbers each can produce covers the range ~[2k, N]~. The intended solution is to use multiples of ~2k+1~ as this covers all the numbers up to ~N~ and the number ~2k+1~ can be used to make the multiples themselves. This requires an array length of ~k+\left\lceil\dfrac{N-k}{2k+1}\right\rceil~ and we can loop through all values of ~k~ to find the one that results in the minimum length.

~\mathcal{O}(N)~

Using calculus, we can determine the optimal value of ~k~ and the minimum length it produces in ~\mathcal{O}(1)~ time. It turns out the minimum length is ~\left\lceil\sqrt{2N+1}\right\rceil-1~, which can be proven to never exceed ~\lfloor\sqrt{2N}\rfloor~.