1362. Closest Divisors
Problem Description
The problem presents a scenario where you are given a single integer num
. Your task is to find two integers whose product is either num + 1
or num + 2
. These two integers should be as close to each other as possible in terms of their absolute difference ā meaning the difference between the two numbers without considering whether it is positive or negative should be minimal. The final solution does not require the integers to be in any specific order, thus either of the integers can come first.
Intuition
In solving this problem, the concept of factors of a number is key. For any given number, its factors are the numbers that divide it without leaving a remainder. In this case, our target numbers are num + 1
and num + 2
. We look for the pair of factors, for each of these numbers, that are closest to each other. The intuition here is that the pair of factors that are closest to each other will have the smallest absolute difference.
To efficiently find such a pair for a given target number, we can start checking from the square root of the target number and move downwards. The square root gives us a good starting point since it is the largest number that can multiply by itself to not exceed the target. Therefore, any factor larger than the square root would result in a product larger than our target number, disqualifying it from being a correct answer.
Once we have the factors for both num + 1
and num + 2
, we compare their absolute differences. The pair with the smaller absolute difference is the closest pair ā this represents our final answer. The reason for checking both num + 1
and num + 2
is to fulfill the task's requirement of finding the closest integers in absolute difference.
Learn more about Math patterns.
Solution Approach
The solution uses a straightforward approach by defining a helper function f(x)
which takes a number x
(which will either be num + 1
or num + 2
) and finds the closest divisors of x
.
Here's how the f(x)
function works in detail:
- Start by calculating the integer square root of
x
usingint(sqrt(x))
. This is the starting point for finding our factors. - Iterate downwards from this square root to 1 (inclusive), as any factor greater than the square root of
x
would result in a product larger thanx
when multiplied with another integer. - In each iteration, check if
x % i == 0
which is the condition to confirm ifi
is a factor ofx
. - Once a factor is found, calculate the pair by dividing
x
by the factori
. The pair will be[i, x // i]
. - Return the pair of factors found.
The main function closestDivisors(num: int) -> List[int]
calls this helper function twice: once with num + 1
and once with num + 2
.
- The function stores the pairs returned by
f(num + 1)
andf(num + 2)
in variablesa
andb
respectively. - It then compares the absolute differences of the two integers in each pair.
- The pair with the smaller absolute difference is chosen as the result.
- The result pair is returned.
Algorithmically, this is an efficient approach because it only searches up to the square root of the target numbers rather than iterating through all possible divisors, which significantly reduces the number of operations, especially for very large numbers.
To summarize, the solution algorithm involves:
- Finding pairs of factors (divisors) for two numbers
num + 1
andnum + 2
. - Starting the search from the square root of these numbers and iterating downwards to find these pairs.
- Returning the pair with the smallest absolute difference between the two factors.
Data structures used in this solution are basic and include primarily lists to store the pairs of factors. The pattern utilized here is an optimization over brute force where only necessary divisors are considered, which is made possible by the mathematical property that a number's divisors are symmetrical around the square root.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's assume num = 8
. We want to find two integers whose product is num + 1
or num + 2
, which here would be 9
and 10
. These two integers should have the smallest possible absolute difference. Let's apply our solution approach:
-
We first calculate the square root of
num + 1
which issqrt(9) = 3
. -
Then, we check if there's any number from 3 down to 1 that evenly divides 9:
- 3 is a divisor of 9 since
9 % 3 == 0
. - The pair is formed by
3
(the divisor) and9 // 3 = 3
. So the factor pair fornum + 1
is[3, 3]
.
- 3 is a divisor of 9 since
-
Next, we calculate the square root of
num + 2
, which is slightly oversqrt(10)
but we useint(sqrt(10)) = 3
as our starting point. -
We check divisors from 3 to 1 for the number 10:
- 3 is not a divisor of 10 since
10 % 3 != 0
. - 2 is a divisor since
10 % 2 == 0
. - The pair for
num + 2
is[2, 10 // 2]
, which is[2, 5]
.
- 3 is not a divisor of 10 since
-
Now we have two pairs:
[3, 3]
fornum + 1
and[2, 5]
fornum + 2
. We compare their absolute differences:- The absolute difference for
[3, 3]
is3 - 3 = 0
. - The absolute difference for
[2, 5]
is5 - 2 = 3
.
- The absolute difference for
-
We choose the pair with the smallest absolute difference, which is
[3, 3]
, with an absolute difference of 0. -
The final result is
[3, 3]
, indicating that these are the two integers (which in this case happen to be identical) that, when multiplied together, yieldnum + 1
(which is 9) and have the smallest absolute difference.
This example walk-through demonstrates the solution approach. By checking only the divisors from the square root and below, we quickly identify the closest pair of numbers satisfying the condition without unnecessary computation.
Solution Implementation
1from typing import List
2from math import sqrt
3
4class Solution:
5 def closestDivisors(self, num: int) -> List[int]:
6 # Define a helper function to find the pair of divisors
7 # of a number 'x' that are closest to each other.
8 def find_closest_divisors(x):
9 # Start by finding the square root of 'x' and iterate backwards
10 for i in range(int(sqrt(x)), 0, -1):
11 # If 'i' is a divisor of 'x'
12 if x % i == 0:
13 # Return the divisor pair [i, x // i]
14 return [i, x // i]
15
16 # Find the closest divisors for 'num + 1'
17 closest_divisors_num_plus_one = find_closest_divisors(num + 1)
18 # Find the closest divisors for 'num + 2'
19 closest_divisors_num_plus_two = find_closest_divisors(num + 2)
20
21 # Compare which pair of divisors has the smallest difference
22 # and return that pair.
23 if abs(closest_divisors_num_plus_one[0] - closest_divisors_num_plus_one[1]) < abs(closest_divisors_num_plus_two[0] - closest_divisors_num_plus_two[1]):
24 return closest_divisors_num_plus_one
25 else:
26 return closest_divisors_num_plus_two
27
1class Solution {
2
3 // This function finds two closest divisors of the input number 'num'
4 public int[] closestDivisors(int num) {
5 // Find the closest divisors for the number 'num + 1'
6 int[] divisorsNumPlusOne = findClosestDivisors(num + 1);
7 // Find the closest divisors for the number 'num + 2'
8 int[] divisorsNumPlusTwo = findClosestDivisors(num + 2);
9
10 // Compare abs difference of divisors pairs and return the pair with the smallest difference
11 if (Math.abs(divisorsNumPlusOne[0] - divisorsNumPlusOne[1]) <
12 Math.abs(divisorsNumPlusTwo[0] - divisorsNumPlusTwo[1])) {
13 return divisorsNumPlusOne;
14 } else {
15 return divisorsNumPlusTwo;
16 }
17 }
18
19 // Helper function that calculates the two closest divisors of 'x'
20 private int[] findClosestDivisors(int x) {
21 // Start from the square root of 'x' and check for the closest divisors by moving downwards
22 for (int i = (int) Math.sqrt(x); true; --i) { // the condition is always true, it breaks inside if a divisor pair is found
23 // If 'i' divides 'x' with no remainder, 'i' and 'x / i' are divisors of 'x'
24 if (x % i == 0) {
25 // Found the closest divisors, return them in an array
26 return new int[] {i, x / i};
27 }
28 }
29 }
30}
31
1#include <vector>
2#include <cmath> // Include cmath for sqrt function
3
4class Solution {
5public:
6 // Function to find the closest divisors of an integer 'num'
7 vector<int> closestDivisors(int num) {
8 // Lambda function to find the divisors closest to the square root of 'x'
9 auto findClosestDivisors = [](int x) -> vector<int> {
10 // Start from the largest possible factor that could be closest to sqrt of x
11 for (int i = sqrt(x); i > 0; --i) { // Ensure i is always positive
12 if (x % i == 0) {
13 // If i is a divisor, return the pair (i, x/i)
14 return vector<int>{i, x / i};
15 }
16 }
17 // This code should never reach here since every number has at least one pair of divisors
18 };
19
20 // Find the closest divisors for both num+1 and num+2
21 vector<int> divisorsForNumPlusOne = findClosestDivisors(num + 1);
22 vector<int> divisorsForNumPlusTwo = findClosestDivisors(num + 2);
23
24 // Determine which pair of divisors has the smallest difference
25 // Return the pair with the smallest difference
26 return abs(divisorsForNumPlusOne[0] - divisorsForNumPlusOne[1]) < abs(divisorsForNumPlusTwo[0] - divisorsForNumPlusTwo[1]) ? divisorsForNumPlusOne : divisorsForNumPlusTwo;
27 }
28};
29
30// Remember to include necessary headers before using this code.
31
1// Import sqrt function from Math module
2import { sqrt, abs } from 'math';
3
4// Function to find closest divisors of an integer 'num'
5function closestDivisors(num: number): number[] {
6 // Lambda function to find the divisors closest to the square root of 'x'
7 const findClosestDivisors = (x: number): number[] => {
8 // Start from the largest possible factor that could be closest to sqrt of x
9 for (let i = Math.floor(sqrt(x)); i > 0; --i) { // Ensure i is always positive
10 if (x % i === 0) {
11 // If i is a divisor, return the pair [i, x/i]
12 return [i, x / i];
13 }
14 }
15 // Since every number has at least one pair of divisors, this line should not be reached.
16 throw new Error("No divisors found"); // To handle edge cases theoretically unreachable
17 };
18
19 // Find the closest divisors for both num+1 and num+2
20 const divisorsForNumPlusOne: number[] = findClosestDivisors(num + 1);
21 const divisorsForNumPlusTwo: number[] = findClosestDivisors(num + 2);
22
23 // Determine which pair of divisors has the smallest difference, and return the pair with the smallest difference
24 return abs(divisorsForNumPlusOne[0] - divisorsForNumPlusOne[1]) < abs(divisorsForNumPlusTwo[0] - divisorsForNumPlusTwo[1])
25 ? divisorsForNumPlusOne
26 : divisorsForNumPlusTwo;
27}
28
Time and Space Complexity
Time Complexity
The time complexity of the function primarily depends on the for
loop within the nested function f(x)
, which iterates over numbers starting from int(sqrt(x))
to 1
.
Since the square root function essentially reduces the number of iterations to the square root of x
, the time complexity for finding the divisors would be O(sqrt(x))
.
Given that the function f(x)
is called twiceāonce for num + 1
and once for num + 2
āthe overall time complexity is then O(sqrt(num + 1) + sqrt(num + 2))
, which simplifies to O(sqrt(num))
, as the higher order term dominates and adding 1 or 2 to num
has a negligible effect for large numbers.
Space Complexity
The space complexity of this algorithm is O(1)
, as the space used does not grow with the input size num
. The only extra space used is for a handful of variables that store the divisor pairs and their differences.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following is a min heap?
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first