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.

#1362

Medium

auto_awesome数学·driven

LeetCode 题解工作台

最接近的因数

给你一个整数 num ，请你找出同时满足下面全部要求的两个整数：两数乘积等于 num + 1 或 num + 2 以绝对差进行度量，两数大小最接近你可以按任意顺序返回这两个整数。示例 1：输入： num = 8 输出： [3,3] 解释：对于 num + 1 = 9，最接近的两个因数是 3…

数学

题目描述

给你一个整数 num，请你找出同时满足下面全部要求的两个整数：

两数乘积等于 num + 1 或 num + 2
以绝对差进行度量，两数大小最接近

你可以按任意顺序返回这两个整数。

示例 1：

输入：num = 8
输出：[3,3]
解释：对于 num + 1 = 9，最接近的两个因数是 3 & 3；对于 num + 2 = 10, 最接近的两个因数是 2 & 5，因此返回 3 & 3 。

示例 2：

输入：num = 123
输出：[5,25]

示例 3：

输入：num = 999
输出：[40,25]

提示：

1 <= num <= 10^9

lightbulb

解题思路

方法一：枚举

我们设计一个函数 $f(x)$ ，该函数返回乘积等于 $x$ 的两个数，且这两个数的差的绝对值最小。我们可以从 $\sqrt{x}$ 开始枚举 $i$ ，如果 $x$ 能被 $i$ 整除，那么 $\frac{x}{i}$ 就是另一个因数，此时我们就找到了一个乘积等于 $x$ 的两个因数，我们将其返回即可。否则我们减小 $i$ 的值，继续枚举。

接下来，我们只需要分别计算 $f(num + 1)$ 和 $f(num + 2)$ ，然后比较两个函数的返回值，返回差的绝对值更小的那个即可。

时间复杂度 $O(\sqrt{num})$ ，空间复杂度 $O(1)$ 。其中 $num$ 是给定的整数。

1

2

3

4

5

6

7

8

9

10

11

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#1363 形成三的最大倍数 #1360 日期之间隔几天 #1359 有效的快递序列数目