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^9To find two numbers whose product is either num + 1 or num + 2, we can utilize the fact that such numbers will be around the square root of these sums. This is due to the mathematical property that for two numbers to multiply to a product, they will be closest when both numbers are as near as possible to the square root of the product.
This C program iterates over num + 1 and num + 2. For each number, it starts from its square root and moves downward to find the closest divisors.
C++
Java
Python
C#
JavaScript
Time Complexity: O(sqrt(num)) for each of num + 1 and num + 2. Thus, O(sqrt(num)) overall.
Space Complexity: O(1) as only a fixed number of variables are used.
Another approach involves iteratively finding divisors for num + 1 and num + 2 starting from 1 up to the square root, and tracking which pair has the smallest difference.
This C implementation scans from 1 to the square root of num + 1 and num + 2. It tracks the pair of divisors with the smallest difference.
C++
Java
Python
C#
JavaScript
Time Complexity: O(sqrt(num))
Space Complexity: O(1)
| Approach | Complexity |
|---|---|
| Square Root Approximation Approach | Time Complexity: O(sqrt(num)) for each of |
| Iterative Minimization Approach | Time Complexity: O(sqrt(num)) |
K Closest Points to Origin - Heap / Priority Queue - Leetcode 973 - Python • NeetCode • 107,738 views views
Watch 9 more video solutions →Practice Closest Divisors with our built-in code editor and test cases.
Practice on FleetCode