Closest Divisors

Medium
703.

Closest Divisors

Closest Divisors is a medium coding problem on math and number theory, asked in Amazon, Adobe and Oracle interviews.

Find two integers whose product is either num + 1 or num + 2 and whose difference is as small as possible.

Return them in ascending order.

Example 1

Input
num = 8
Output
[3,3]
Explanation
9 = 3 × 3 is a perfect square, so the gap is 0.

Example 2

Input
num = 123
Output
[5,25]
Explanation
125 = 5 × 25 has gap 20, beating 124 = 4 × 31 with gap 27.

Example 3

Input
num = 999
Output
[25,40]
Explanation
1000 = 25 × 40 has gap 15; the best factorisation of 1001 is 13 × 77.

Constraints

  • 1 <= num <= 10000000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} num
 * @return {number[]}
 */
var closestDivisors = function(num) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Closest Divisors — Solution in Python, Java & C++

Closest Divisors solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Closest Divisors is a medium coding problem on math and number theory, asked in Amazon, Adobe and Oracle interviews.

  • Difficulty: Medium
  • Topics: Math, Number Theory
  • Asked at: Amazon, Adobe, Oracle
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Find two integers whose product is either num + 1 or num + 2 and whose difference is as small as possible.

Return them in ascending order.

Example 1

Input: num = 8
Output: [3,3]
Explanation: 9 = 3 × 3 is a perfect square, so the gap is 0.

Example 2

Input: num = 123
Output: [5,25]
Explanation: 125 = 5 × 25 has gap 20, beating 124 = 4 × 31 with gap 27.

Example 3

Input: num = 999
Output: [25,40]
Explanation: 1000 = 25 × 40 has gap 15; the best factorisation of 1001 is 13 × 77.

Constraints

  • 1 <= num <= 10000000

Hints for Closest Divisors

  1. Hint 1

    Solve the sub-problem 'closest factor pair of t' and run it for t = num + 1 and t = num + 2.

  2. Hint 2

    The closest pair straddles sqrt(t), so walk down from floor(sqrt(t)) to the first divisor.

  3. Hint 3

    Then take whichever of the two targets gives the smaller gap.

How to solve Closest Divisors

There are only two candidate products. For each, the most balanced factor pair is found by walking down from the square root to the first divisor; then compare the two gaps.

Approach

  1. For t in {num + 1, num + 2}: set w = floor(sqrt(t)) and decrement until t % w == 0.
  2. The pair is [w, t / w], with gap t / w - w.
  3. Return whichever pair has the smaller gap.

Why it works

For a fixed product, the gap t/d - d shrinks as d rises towards sqrt(t), so the largest divisor at or below the square root is the balanced one. Checking both targets is exhaustive because the statement allows exactly those two.

Complexity

  • Time — O(sqrt(num))
  • Space — O(1)

Pitfalls

  • Floating-point sqrt can overshoot by one on a perfect square — guard with while (w * w > t) w--.
  • Returning the pair for num + 1 without comparing against num + 2 misses the better answer roughly half the time.
  • w = 1 always divides, so the loop always terminates.

Reference solution

Python

from typing import List

def closestDivisors(num: int) -> List[int]:
    def best_pair(t: int) -> List[int]:
        w = int(t ** 0.5)
        while w * w > t:
            w -= 1
        while t % w != 0:
            w -= 1
        return [w, t // w]

    a = best_pair(num + 1)
    b = best_pair(num + 2)
    return a if a[1] - a[0] <= b[1] - b[0] else b

Java

public static int[] closestDivisors(int num) {
    int[] a = bestPairDiv(num + 1);
    int[] b = bestPairDiv(num + 2);
    return (a[1] - a[0] <= b[1] - b[0]) ? a : b;
}

static int[] bestPairDiv(int t) {
    int w = (int) Math.sqrt(t);
    while ((long) w * w > t) w--;
    while (t % w != 0) w--;
    return new int[] { w, t / w };
}

C++

static vector<int> bestPairDiv(int t) {
    int w = (int) sqrt((double) t);
    while ((long long) w * w > t) w--;
    while (t % w != 0) w--;
    return { w, t / w };
}

vector<int> closestDivisors(int num) {
    vector<int> a = bestPairDiv(num + 1);
    vector<int> b = bestPairDiv(num + 2);
    return (a[1] - a[0] <= b[1] - b[0]) ? a : b;
}

JavaScript

var closestDivisors = function(num) {
    var bestPair = function(t) {
        var w = Math.floor(Math.sqrt(t));
        while (w * w > t) w--;
        while (t % w !== 0) w--;
        return [w, t / w];
    };
    var a = bestPair(num + 1);
    var b = bestPair(num + 2);
    return (a[1] - a[0] <= b[1] - b[0]) ? a : b;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 337 math problems · the whole catalogue