We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Closest Divisors

Number: 1276

Difficulty: Medium

Paid? No

Companies: Amazon

Problem Description

Given an integer num, the task is to find a pair of positive integers (a, b) such that either a * b equals num + 1 or num + 2. Among the two possible target numbers (num+1 and num+2), we are to choose the pair of divisors that have the smallest absolute difference between them. The returned pair can be in any order.

Key Insights

  • We only need to consider two candidate numbers: num+1 and num+2.
  • For each candidate, the pair of divisors with the smallest difference is the one where one element is closest to the square root of the candidate.
  • By iterating from the square root downwards, the first valid divisor found gives the pair with the minimum difference for that candidate.
  • Compare the two pairs obtained from num+1 and num+2, and select the one with the smaller absolute difference.

Space and Time Complexity

Time Complexity: O(√(num)) per candidate, so overall O(√(num)). Space Complexity: O(1), aside from the output storage.

Solution

The solution iterates over the two candidate numbers: num+1 and num+2. For each candidate:

  1. Compute the integer square root.
  2. Iterate downward from the square root to 1.
  3. When a divisor i is found such that candidate mod i equals 0, calculate its pair j = candidate / i.
  4. Since the iteration starts at the square root, the first found pair minimizes the difference j - i for that candidate.
  5. Track the pair with the smallest absolute difference across both candidates. This approach efficiently finds the desired pair using basic iteration and integer arithmetic while ensuring optimal performance given the constraints.

Code Solutions

# Python solution with comments

import math

def closestDivisors(num):
    # Initialize best pair and its difference
    best_pair = None
    best_diff = float('inf')
    
    # Iterate through the two candidate numbers: num+1 and num+2
    for candidate in [num + 1, num + 2]:
        # Start from the integer square root and iterate downward
        for i in range(int(math.sqrt(candidate)), 0, -1):
            # If i divides candidate, find its complementary divisor j
            if candidate % i == 0:
                j = candidate // i
                diff = abs(j - i)
                # Update best pair if a smaller difference is found
                if diff < best_diff:
                    best_diff = diff
                    best_pair = [i, j]
                break  # The first found pair minimizes the difference for this candidate
    return best_pair

# Example usage:
print(closestDivisors(8))  # Expected output: [3, 3]
← Back to All Questions