Codesignal Solution: Near Square

Original Problem

You're given a positive integer n. Your task is to represent this number as a product of two positive integers a and b, such that a * b = n, a ≤ b, and the difference b - a is the smallest possible.

Return the answer as an array of two elements [a, b].

Example

For n = 10, the output should be

Near_Square(n) = [2, 5].

It's possible to write 10 in two ways: 2 * 5 = 10, or 1 * 10 = 10. The 2 * 5 = 10 representation has the smallest difference (b - a = 5 - 2 = 3), so the answer is [2, 5].

Input/Output

• [time limit] 4000ms (js)

• [input] integer n

  Constraints:
  
  1 ≤ n ≤ 2 · 10⁹.

• [output] array.integer

  Array of two elements, whose product equals n.

Solution

The main idea to tackle this problem is to think of what minimizes the distance \(b-a\). The minimum for \(n\) being square would be zero, if \(a=b\) and therefore \(a^2=n\). That means the minimum for the general case must be the first divider of \(n\) with minimal distance from the square root of \(n\). We have two options now, we can either count \(b\) up, beginning with \(b_0=\lceil\sqrt{n}\rceil\) or \(a\) down beginning with \(a_0=\lfloor\sqrt{n}\rfloor\). As soon as we find one \(a\) (or \(b\)) which devides \(n\), we must have found the solution. An implementation can then look as follows:

Near_Square = n => {
 a = Math.sqrt(n) | 0
 while (n % a) a--
 return [a, n / a]
}

That's pretty short already, but we could remove the manual calculation of the integer square root by working upwards towards the square root of \(n\). For each iteration we have to check if the current number is a divisor and if it is, we got a new candidate. The candidate which remains the last, is our solution. As an implementation, this means:

Near_Square = n => {
 r = null
 for (a = 1; a * a < n; a++)
  if (n % a == 0)
   r = [a, n / a]
 return r
}

This algorithm can be packed into an eval block and some expressions can be re-formulated in a shorter form to come up with:

Near_Square=n => eval('for(a = 0; a++ * a < n; ) r = n % a ? r : [a, n / a]')