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=\lceil {\displaystyle \frac{N+1}{6}}\rceil$. This results in a length of $2k+1=2\lceil {\displaystyle \frac{N+1}{6}}\rceil +1$, which approaches ${\displaystyle \frac{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+\lceil {\displaystyle \frac{N-k}{2k+1}}\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 $\lceil \sqrt{2N+1}\rceil -1$, which can be proven to never exceed $\lfloor \sqrt{2N}\rfloor$.