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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Closest Divisors

Difficulty: Medium

Problem Description

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.

Key Insights

  • The problem requires finding two integers whose product matches either num + 1 or num + 2.
  • The closest integers will be those that are nearest to the square root of the target product since products of two numbers are closest when the numbers are close to each other.
  • We can check divisors up to the square root of the number to find potential pairs.

Space and Time Complexity

Time Complexity: O(sqrt(n))
Space Complexity: O(1)

Solution

To solve the problem, we will:

  1. Calculate two potential target values: target1 = num + 1 and target2 = num + 2.
  2. For each target, iterate from 1 to the square root of the target to find divisors.
  3. For each divisor i, check if i and target / i are valid pairs.
  4. Keep track of the pair with the smallest absolute difference and return it.

Code Solutions

def closest_divisors(num):
    def find_closest_factors(n):
        closest = (1, n)  # Start with the pair (1, n)
        for i in range(1, int(n**0.5) + 1):
            if n % i == 0:
                j = n // i
                if abs(i - j) < abs(closest[0] - closest[1]):
                    closest = (i, j)
        return closest

    target1 = num + 1
    target2 = num + 2
    closest1 = find_closest_factors(target1)
    closest2 = find_closest_factors(target2)

    return closest1 if abs(closest1[0] - closest1[1]) <= abs(closest2[0] - closest2[1]) else closest2
← Back to All Questions