Given a positive integer $k$, let $||k||$ denote the absolute difference between $k$ and the nearest perfect square. For example, $||13||=3$  since the nearest perfect square to $13$ is $16$. Compute the smallest positive integer $n$ such that $\frac{||1|| + ||2|| + ...+ ||n||}{n}=100$.

Let's think step by step and output the final answer within \boxed{}.
user