LeetCode Closest Divisors

1362. Closest Divisors

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.

Example 1:

Input: num = 8
Output: [3,3]
Explanation: 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 3:

Input: num = 999
Output: [40,25]

Constraints:

  • 1 <= num <= 10^9

给定一个数num,找出所有a*b等于num+1或num+2的(a,b)组合中,a和b的差最小的那个组合。

子问题就是给定一个数num,找出a*b==num的(a,b)组合中,a和b的差最小的组合。根据反证法,a和b必定有一个小于等于sqrt(num),另一个大于等于sqrt(num)。所以我最开始的做法是,用之前快速求sqrt的方法,计算sqrt(num),令left和right都等于sqrt(num),然后判断left*right的积,如果大于num,则–right;否则++left。这样虽然能得到正确结果,但提交后TLE。

百思不得其解,后来看别人的解答,才理解为什么我会TLE。我的解法设置了left和right两个指针,根据乘积的大小关系,left和right都在移动,在某些情况总的移动数会很大。而正确解法是,只设置一个移动指针i,i从sqrt(num)递减,然后判断num是否能整除i,如果能整除,则肯定找到一个因式分解。这种方法相当于我的方法中只移动了left,速度快了不少。在这种解法下,用不用快速sqrt都能AC。

完整代码如下:

class Solution {
public:
	int mySqrt(int x)
	{
		long long y = x;
		while (y*y > x)
		{
			y = (y + x / y) / 2;
		}
		return y;
	}

	vector<int> work(int num) {
		for (int i = mySqrt(num) + 1; i >= 1; --i) {
			if (num%i == 0) {
				return { i,num / i };
			}
		}
		return { 1,num };
	}
	vector<int> closestDivisors(int num) {
		vector<int> plus1 = work(num + 1);
		vector<int> plus2 = work(num + 2);
		if (abs(plus1[1] - plus1[0]) < abs(plus2[1] - plus2[0]))return plus1;
		else return plus2;
	}
};

Leave a Reply

Your email address will not be published. Required fields are marked *