Domain 2MediumMEDIUM

Closest Divisors

Find closest divisor pair for num+1 or num+2 by iterating from sqrt(target) downwards to minimize absolute difference.

Domain: medium•Updated: 2026-09-15
#math#array#O(sqrt(N)) time complexity#O(1) space complexity

Problem Breakdown

We are given an integer num and need to find a factor pair (a,b)(a, b) such that a×ba \times b equals either num + 1 or num + 2. Among all valid pairs for both targets combined, we must select the one where the absolute difference between factors (∣a−b∣|a - b|) is minimized. The solution involves evaluating two specific target numbers and comparing their optimal factorizations.

Intuition

For any integer PP, a pair of divisors (a,b)(a, b) with product PP has its minimum absolute difference when both factors are as close to P\sqrt{P} as possible. If we iterate downwards from int(sqrt(P)), the first divisor encountered will yield the largest factor less than or equal to P\sqrt{P}. This guarantees minimal difference for that specific target number immediately, without needing to check all divisors. We apply this logic separately to num+1num + 1 and num+2num + 2, then compare results.

Approach

  1. Define a helper function get_best_pair(target) which calculates the integer square root of target.
  2. Iterate downwards from that floor(sqrt) value until a divisor is found. The first match gives the optimal pair for that target.
  3. Compute this best pair for both num+1num + 1 and num+2num + 2.
  4. Calculate absolute differences (∣a−b∣|a - b|) for both pairs.
  5. Return the pair associated with the smaller difference (prioritizing num+1 if differences are equal).

Complexity Analysis

  • Time Complexity: O(N)O(\sqrt{N}), where N≈num+2N \approx num + 2. In the worst case (when target is prime), we iterate from target\sqrt{target} down to 1. For num=109num = 10^9, this involves roughly 31,622 iterations maximum, which fits within standard time limits (∼108\sim 10^8 ops/sec).
  • Space Complexity: O(1)O(1) as we only store a few variables and pairs during iteration without recursion or auxiliary data structures.

Solution

import math
from typing import List

def closestDivisors(num: int) -> List[int]:
    # Helper to find the pair with minimal difference for a specific target number
    def get_best_pair(target):
        start = math.isqrt(target)  # Integer square root is safe and precise
        
        while True:
            if target % start == 0:
                return [start, target // start]
            start -= 1
            
    t1 = num + 1
    pair1 = get_best_pair(t1)
    
    t2 = num + 2
    pair2 = get_best_pair(t2)
    
    diff1 = abs(pair1[0] - pair1[1])
    diff2 = abs(pair2[0] - pair2[1])
    
    # Return the pair with strictly smaller difference. 
    # If differences are equal, returning either is valid per problem constraints usually.
    if diff1 <= diff2:
        return pair1
    else:
        return pair2

# Example usage (uncomment for local testing)
# print(closestDivisors(8))   # Output: [3, 3]
# print(closestDivisors(123)) # Output: [5, 25]

Edge Cases Handled

  • Prime Targets: If num + 1 or num + 2 is prime (e.g., num=97 -> targets 98, 99; if target was prime like 97), the loop correctly falls back to divisor 1, returning [1, target].
  • Perfect Squares: If a target is a perfect square (e.g., num+1=9num+1 = 9), the starting point of iteration hits exactly target\sqrt{target} immediately. This returns [3, 3] with difference 0, which is optimal.
  • Small Inputs: For num=1, targets are 2 and 3. Loop runs quickly (start at floor(sqrt)). Returns correct pairs based on minimal diff logic.