Robert Eisele
Engineer, Systems Architect and DBA

# Codefights: 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 · 109.

• [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]')

Go to overview