#1362

Medium

auto_awesomeMath-driven solution strategy

LeetCode Problem Workspace

Closest Divisors

Find the closest divisors of num + 1 and num + 2 with minimal absolute difference in this math-driven problem.

Problem Statement

Given an integer num, you need to find two integers whose product is either num + 1 or num + 2. These two integers should have the closest possible absolute difference. The two numbers can be returned in any order, as long as their product matches one of the two possible values.

For example, with num = 8, num + 1 = 9 and num + 2 = 10. The closest pair of divisors for 9 are 3 & 3, and for 10, they are 2 & 5. Since 3 & 3 has the smallest absolute difference, it’s chosen as the solution.

Examples

Example 1

Input: num = 8

Output: [3,3]

For num + 1 = 9, the closest divisors are 3 & 3, for num + 2 = 10, the closest divisors are 2 & 5, hence 3 & 3 is chosen.

Example 2

Input: num = 123

Output: [5,25]

Example details omitted.

Example 3

Input: num = 999

Output: [40,25]

Example details omitted.

Constraints

1 <= num <= 10^9

Solution Approach

Divisor Search

Start by calculating the divisors of num + 1 and num + 2. Iterate over potential divisors up to the square root of these values, and check which pairs multiply to the given numbers.

Minimize Difference

After finding the divisor pairs, compare the absolute differences between each pair. The pair with the smallest difference is the one you should return.

Efficient Calculation

Optimize the divisor search by only considering divisors up to the square root of num + 1 and num + 2. This reduces unnecessary calculations and improves performance.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is determined by the divisor search. For each num, you need to check up to sqrt(num+1) and sqrt(num+2), so the time complexity is O(sqrt(num)). The space complexity is O(1), as the divisor pairs are calculated without storing large amounts of data.

What Interviewers Usually Probe

Candidate understands the properties of divisors and can apply them efficiently.
Candidate can optimize solutions based on mathematical properties, such as limiting the divisor range to the square root.
Candidate can explain how they minimized the absolute difference and why that’s the optimal approach.

Common Pitfalls or Variants

Common pitfalls

Not limiting the divisor search to the square root of num + 1 and num + 2, leading to inefficient solutions.
Overcomplicating the problem by checking too many divisor pairs without focusing on minimizing the absolute difference.
Confusing the problem by returning divisors without considering the smallest absolute difference.

Follow-up variants

Allow for multiple valid pairs of divisors with different absolute differences, but still require choosing the pair with the smallest difference.
Extend the problem to find the closest divisors for num + 1, num + 2, and num + 3.
Add constraints that require finding the pair of divisors that are both prime.

FAQ

What is the best approach to solve the Closest Divisors problem?

The best approach is to first find the divisors of num + 1 and num + 2, then compare the divisor pairs and choose the one with the smallest absolute difference.

Why should we only check divisors up to the square root of num + 1 or num + 2?

Checking divisors up to the square root is efficient because divisors come in pairs, and you only need to consider one divisor of each pair to find both divisors.

How do I minimize the absolute difference between divisor pairs?

After finding all divisor pairs, calculate the absolute difference for each pair. The pair with the smallest difference is the correct answer.

Can there be more than one valid answer in the Closest Divisors problem?

Yes, but you should always return the pair with the smallest absolute difference. If multiple pairs have the same difference, any of them can be returned.

How does GhostInterview help with the Closest Divisors problem?

GhostInterview provides clear steps to find divisors efficiently, minimizes unnecessary calculations, and helps you understand how to apply mathematical strategies to solve the problem.

terminal

Solution

Solution 1: Enumeration

We design a function $f(x)$ that returns two numbers whose product equals $x$ and the absolute difference between these two numbers is the smallest. We can start enumerating $i$ from $\sqrt{x}$. If $x$ can be divided by $i$, then $\frac{x}{i}$ is another factor. At this point, we have found two factors whose product equals $x$. We can return them directly. Otherwise, we decrease the value of $i$ and continue to enumerate.

1

2

3

4

5

6

7

8

9

10

class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        def f(x):
            for i in range(int(sqrt(x)), 0, -1):
                if x % i == 0:
                    return [i, x // i]

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

Continue Practicing

#1363 largest multiple of three #1360 number of days between two dates #1359 count all valid pickup and delivery options