Codesignal Solution: nextSquare

Original Problem

Given an integer n, return the smallest integer a, such that a is a square of some integer and is greater than n.

Example

For n = 5, the output should be
nextSquare(n) = 9.

Input/Output

• [time limit] 4000ms (js)

• [input] integer n

  Guaranteed constraints:
  1 ≤ n < 2³¹.

• [output] integer

  The smallest square that is greater than n.

Solution

We are searching for the smallest \(a\) such that \(n<a\), with \(a=m^2, m\in\mathbb{N}\). That means that

\[ \begin{array}{rl} &n<a\\ \Leftrightarrow & n <m^2\\ \Leftrightarrow & \sqrt{n} <m\\ \Rightarrow & 1+\lfloor\sqrt{n}\rfloor =m\\ \Leftrightarrow & m=- \sim\sqrt{n}\\ \Leftrightarrow & m^2=(\sim\sqrt{n})^2 \end{array} \]

Note, that we don't ceil the square root, since perfect squares need to skip to the next square as well. So flooring and adding one is the solution. Removing the floor syntactically is mathematically not neat but it is based on the JavaScript feature that using a binary operator with a double implicitly casts to integer (which is equal to floor, since we have positive roots only). Using not (\(\sim)\) and flipping the sign again adds one, due to the two's complement representation of numbers. Since we square the number, the negative sign is redundant anyway. Implemented in JavaScript, the whole thing looks like:

nextSquare = n => (~Math.sqrt(n)) ** 2