Closest Divisors - Practice Coding Problems

Closest Divisors - Problem

Math Medium

Given an integer num, find the closest two integers in absolute difference whose product equals num + 1 or num + 2.

Return the two integers in any order.

Example: If num = 8, we need to find two integers whose product is either 9 or 10. For 9: divisors are [1,9] and [3,3]. For 10: divisors are [1,10], [2,5]. The closest pair is [3,3] with difference 0.

Input & Output

Example 1 — Perfect Square Case

$ Input: num = 8

› Output: [3,3]

💡 Note: For num+1=9: divisors are [1,9] and [3,3]. For num+2=10: divisors are [1,10], [2,5]. The closest pair is [3,3] with difference 0.

Example 2 — Small Number

$ Input: num = 2

› Output: [2,2]

💡 Note: For num+1=3: divisors are [1,3]. For num+2=4: divisors are [1,4], [2,2]. The closest pair is [2,2] with difference 0.

Example 3 — Prime Result

$ Input: num = 10

› Output: [3,4]

💡 Note: For num+1=11: divisors are [1,11] (11 is prime). For num+2=12: divisors include [3,4]. The closest pair is [3,4] with difference 1.

Constraints

1 ≤ num ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Given integer num = 8

Process

Find divisors of num+1=9 and num+2=10, choose closest pair

Output

Return [3,3] as it has minimum difference of 0

Key Takeaway

🎯 Key Insight: The closest divisors are always found near the square root of the target number

Asked in

F Facebook 25 a Amazon 20

The key insight is that the closest divisors of any number are found near its square root. Start from floor(sqrt(target)) and work downward - the first divisor found gives the optimal pair. Check both num+1 and num+2, return the pair with minimum difference. Best approach is Square Root Optimization. Time: O(√n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Square Root Optimization	O(√n)	O(1)	Start from square root and work downward to find closest divisors efficiently
Brute Force - Check All Divisors	O(n)	O(1)	Find all divisor pairs for both num+1 and num+2, return the closest pair

Square Root Optimization — Algorithm Steps

For each target (num+1, num+2)
Start from floor(sqrt(target)) and iterate downward
Find first divisor i where target % i == 0
Return the pair [i, target/i] with minimum difference

Visualization

Tap to expand

Step-by-Step Walkthrough

Start from √n

Begin at floor(sqrt(target)) and go down

Find First Divisor

First divisor found gives closest pair

Compare Results

Choose better result between num+1 and num+2

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

void findClosestDivisors(int n, int* result) {
    // Start from square root and go down
    for (int i = (int) sqrt(n); i >= 1; i--) {
        if (n % i == 0) {
            result[0] = i;
            result[1] = n / i;
            return;
        }
    }
    result[0] = 1;
    result[1] = n; // Fallback
}

void solution(int num, int* result) {
    int pair1[2], pair2[2];
    
    findClosestDivisors(num + 1, pair1);
    findClosestDivisors(num + 2, pair2);
    
    int diff1 = abs(pair1[0] - pair1[1]);
    int diff2 = abs(pair2[0] - pair2[1]);
    
    if (diff1 <= diff2) {
        result[0] = pair1[0];
        result[1] = pair1[1];
    } else {
        result[0] = pair2[0];
        result[1] = pair2[1];
    }
}

int main() {
    int num;
    scanf("%d", &num);
    
    int result[2];
    solution(num, result);
    
    printf("[%d,%d]\n", result[0], result[1]);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(√n)

We only iterate from square root down to 1, and stop at first divisor found

✓ Linear Growth

Space Complexity

O(1)

Only using a few variables to track the best pair

✓ Linear Space

32.0K Views

Medium Frequency

~15 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Square Root Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler