Find the Closest Pair of Factors for a Given Number

Find the closest pair of factors for a given number.

More formally, given a number n, write it as a product of two numbers a and b such that | a - b | is the minimum of all combinations.

Example

For example, given a number 812848, it can be written as the product of two numbers in the following different ways:

1 × 812848 = 812,848
2 × 406424 = 812,848
4 × 203212 = 812,848
8 × 101606 = 812,848
16 × 50803 = 812,848
101 × 8048 = 812,848
202 × 4024 = 812,848
404 × 2012 = 812,848
503 × 1616 = 812,848

808 × 1006 = 812,848

Our required answer is the last product (808 × 1006).

abs(808 - 1006) = 198 is the smallest difference among all other combinations.

Approach

Regardless of whether n is a perfect square, if we try to find its square root, we obtain a real root for all n ∈ R.

Only considering the integer part of the square root, we can then iterate by increasing upon it with a step difference of 1 until we find a value for when the product equals given n.

So, every time we compute the integer square root, it's assumed to be one of the factors while the other factor would be the integer quotient. Both are updated on every iteration until we reach a point where their product equals n.

Implementation in Python

def closestPair(n):

    a = b = int(n ** 0.5)

    while (a * b) != n:

        a += 1

        b = n // a

    return a, b

Both factors are initialized as the integer of square root of the given number n. We run a while loop as long their product doesn't equal given n.

In every iteration, we increment one of the factors, say a, by 1 while assigning the other factor, say b, with the integer quotient of the most recent value of a. The loop surely ends when both a and b are factors of the given number n and returns them both.

In the case of a prime number, the value of a increments by 1 until it reaches the value of n itself while b (obviously) reaches 1. This is valid because prime numbers only have two factors (1 and itself).

Time Complexity
O(n)

Space Complexity

O(1)