Jobs

Interviews

Discussions

Closest Divisors

Medium

Asked by:

24 views

Topics:

ArraysTwo Pointers

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

Try coding it in LeetCode

Closest Divisors

Medium

Asked by:

24 views

Topics:

ArraysTwo Pointers

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of the input integer 'num'? Can 'num' be zero or negative?
If there are multiple pairs of divisors with the same minimum difference, is any one of them acceptable, or is there a specific preference?
If 'num' is 0, what output is expected?
Are we guaranteed that at least one pair of divisors exists for 'num + 1' or 'num + 2'?
Could you provide a few examples of input values and their expected outputs, especially around edge cases like small numbers?

Brute Force Solution

Approach

The brute force approach to finding closest divisors is like testing every possible combination. We systematically check each pair of numbers to see if they divide the given number (or number + 1) and then compare how close they are.

Here's how the algorithm would work step-by-step:

Start by considering the number itself and the number right after it.
Find all the pairs of whole numbers that, when multiplied together, equal the number you're looking at, or the number right after it. Think of listing all the factors of each number.
For each pair of factors you find, calculate the difference between the two numbers in the pair.
Keep track of the pair that has the smallest difference.
The pair with the smallest difference is your answer – those are the closest divisors.

Code Implementation

def closest_divisors_brute_force(number):    closest_divisors = [1, number]
    min_difference = number - 1

    # Iterate through the number and the number plus one
    for current_number in [number, number + 1]:
        # Find all pairs of factors for the current number
        for first_divisor in range(1, int(current_number**0.5) + 1):
            if current_number % first_divisor == 0:

                second_divisor = current_number // first_divisor

                #Calculate difference between the divisors
                difference = abs(first_divisor - second_divisor)

                # Update closest divisors if a closer pair is found
                if difference < min_difference:
                    min_difference = difference
                    closest_divisors = [first_divisor, second_divisor]

    return closest_divisors

Big(O) Analysis

Time Complexity

O(sqrt(n)) – The algorithm iterates through potential divisors up to the square root of n and n+1 to find factor pairs. For each number (n and n+1), finding all divisor pairs involves iterating up to its square root. Since the dominant operation is finding these divisor pairs, and we do this for at most two numbers (n and n+1), the time complexity is determined by the square root operation. Thus, the time complexity is O(sqrt(n)).

Space Complexity

O(sqrt(N)) – The provided solution finds factors by iterating up to the square root of N and N+1, where N is the input number. While finding factor pairs, it implicitly stores these factor pairs. In the worst case, the number of factors can be proportional to the square root of N. Thus, auxiliary space is used to store potentially O(sqrt(N)) factor pairs. Therefore, the overall space complexity is O(sqrt(N)).

Optimal Solution

Approach

The goal is to find two numbers that multiply to either the input number or one more than it, and are as close to each other as possible. We can do this efficiently by starting from the square root and working downwards, checking for divisibility.

Here's how the algorithm would work step-by-step:

Calculate the approximate square root of the input number.
Start checking divisibility from that square root downwards.
For the input number, check if the current number divides it evenly. If it does, you've found a divisor. The input number divided by this divisor is the other divisor.
Also, consider the input number plus one. Check if the current number divides this new number evenly. If it does, you've found a divisor for this new number. The new number divided by this divisor is the other divisor.
Compare the pairs of divisors you found for both the input number and the input number plus one. Choose the pair that has the smallest difference between the two numbers.
Return the chosen pair.

Code Implementation

import math

def closest_divisors(number):
    square_root = int(math.sqrt(number))

    best_difference = float('inf')
    best_pair = []

    for current_divisor in range(square_root, 0, -1):
        # Check for divisibility for the input number.
        if number % current_divisor == 0:
            other_divisor = number // current_divisor
            difference = abs(current_divisor - other_divisor)

            if difference < best_difference:
                best_difference = difference
                best_pair = [current_divisor, other_divisor]

        # Also check for n + 1 divisibility, finding closest divisors
        number_plus_one = number + 1

        if number_plus_one % current_divisor == 0:
            other_divisor = number_plus_one // current_divisor
            difference = abs(current_divisor - other_divisor)

            # Check if new divisors are closer than current best.
            if difference < best_difference:
                best_difference = difference
                best_pair = [current_divisor, other_divisor]

    return best_pair

Big(O) Analysis

Time Complexity

O(sqrt(n)) – The algorithm's dominant operation is iterating downwards from the square root of the input number, n, checking for divisors. The loop continues until a divisor is found for either n or n+1. Therefore, the number of iterations is bounded by the square root of n. Comparing the two potential divisor pairs takes constant time. Thus, the time complexity is O(sqrt(n)).

Space Complexity

O(1) – The algorithm primarily uses a few variables to store the closest divisor pair found so far. It also uses a variable for the square root approximation and for the current divisor being checked. The number of these variables does not scale with the input number, N. Therefore, the auxiliary space required remains constant regardless of the size of the input.

Edge Cases

Case	How to Handle
Input number is 0	Return null or throw an exception since divisors of 0 are undefined, preventing division by zero errors.
Input number is 1	Return (1,1) since 1 is the only divisor and it is closest to itself.
Input number is a large perfect square	The closest divisors would be the square root of the number with itself, which can be handled through typical iteration.
Input number is very large (close to integer limit)	Ensure the multiplication of factors doesn't lead to integer overflow by using a larger data type or careful checks.
Input number is a prime number	The only divisors are 1 and the number itself, handled correctly by the iteration to find divisors.
Input number is negative	Return null or throw an exception since this problem typically deals with positive integers.
Number has multiple divisor pairs with the same minimal difference	Return the first encountered pair or define a clear tie-breaking criteria such as returning the pair with the smaller first element.
Floating-point precision issues (if square root is used)	Avoid relying on exact equality checks when comparing floating-point numbers from square root calculations; use a tolerance.

Input number is 0

How to Handle:

Return null or throw an exception since divisors of 0 are undefined, preventing division by zero errors.

Input number is 1

How to Handle:

Return (1,1) since 1 is the only divisor and it is closest to itself.

Input number is a large perfect square

How to Handle:

The closest divisors would be the square root of the number with itself, which can be handled through typical iteration.

Input number is very large (close to integer limit)

How to Handle:

Ensure the multiplication of factors doesn't lead to integer overflow by using a larger data type or careful checks.

Input number is a prime number

How to Handle:

The only divisors are 1 and the number itself, handled correctly by the iteration to find divisors.

Input number is negative

How to Handle:

Return null or throw an exception since this problem typically deals with positive integers.

Number has multiple divisor pairs with the same minimal difference

How to Handle:

Return the first encountered pair or define a clear tie-breaking criteria such as returning the pair with the smaller first element.

Floating-point precision issues (if square root is used)

How to Handle:

Avoid relying on exact equality checks when comparing floating-point numbers from square root calculations; use a tolerance.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of the input integer 'num'? Can 'num' be zero or negative?
If there are multiple pairs of divisors with the same minimum difference, is any one of them acceptable, or is there a specific preference?
If 'num' is 0, what output is expected?
Are we guaranteed that at least one pair of divisors exists for 'num + 1' or 'num + 2'?
Could you provide a few examples of input values and their expected outputs, especially around edge cases like small numbers?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by considering the number itself and the number right after it.
Find all the pairs of whole numbers that, when multiplied together, equal the number you're looking at, or the number right after it. Think of listing all the factors of each number.
For each pair of factors you find, calculate the difference between the two numbers in the pair.
Keep track of the pair that has the smallest difference.
The pair with the smallest difference is your answer – those are the closest divisors.

Code Implementation

def closest_divisors_brute_force(number):    closest_divisors = [1, number]
    min_difference = number - 1

    # Iterate through the number and the number plus one
    for current_number in [number, number + 1]:
        # Find all pairs of factors for the current number
        for first_divisor in range(1, int(current_number**0.5) + 1):
            if current_number % first_divisor == 0:

                second_divisor = current_number // first_divisor

                #Calculate difference between the divisors
                difference = abs(first_divisor - second_divisor)

                # Update closest divisors if a closer pair is found
                if difference < min_difference:
                    min_difference = difference
                    closest_divisors = [first_divisor, second_divisor]

    return closest_divisors

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Calculate the approximate square root of the input number.
Start checking divisibility from that square root downwards.
For the input number, check if the current number divides it evenly. If it does, you've found a divisor. The input number divided by this divisor is the other divisor.
Also, consider the input number plus one. Check if the current number divides this new number evenly. If it does, you've found a divisor for this new number. The new number divided by this divisor is the other divisor.
Compare the pairs of divisors you found for both the input number and the input number plus one. Choose the pair that has the smallest difference between the two numbers.
Return the chosen pair.

Code Implementation

import math

def closest_divisors(number):
    square_root = int(math.sqrt(number))

    best_difference = float('inf')
    best_pair = []

    for current_divisor in range(square_root, 0, -1):
        # Check for divisibility for the input number.
        if number % current_divisor == 0:
            other_divisor = number // current_divisor
            difference = abs(current_divisor - other_divisor)

            if difference < best_difference:
                best_difference = difference
                best_pair = [current_divisor, other_divisor]

        # Also check for n + 1 divisibility, finding closest divisors
        number_plus_one = number + 1

        if number_plus_one % current_divisor == 0:
            other_divisor = number_plus_one // current_divisor
            difference = abs(current_divisor - other_divisor)

            # Check if new divisors are closer than current best.
            if difference < best_difference:
                best_difference = difference
                best_pair = [current_divisor, other_divisor]

    return best_pair

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input number is 0	Return null or throw an exception since divisors of 0 are undefined, preventing division by zero errors.
Input number is 1	Return (1,1) since 1 is the only divisor and it is closest to itself.
Input number is a large perfect square	The closest divisors would be the square root of the number with itself, which can be handled through typical iteration.
Input number is very large (close to integer limit)	Ensure the multiplication of factors doesn't lead to integer overflow by using a larger data type or careful checks.
Input number is a prime number	The only divisors are 1 and the number itself, handled correctly by the iteration to find divisors.
Input number is negative	Return null or throw an exception since this problem typically deals with positive integers.
Number has multiple divisor pairs with the same minimal difference	Return the first encountered pair or define a clear tie-breaking criteria such as returning the pair with the smaller first element.
Floating-point precision issues (if square root is used)	Avoid relying on exact equality checks when comparing floating-point numbers from square root calculations; use a tolerance.

Input number is 0

How to Handle:

Return null or throw an exception since divisors of 0 are undefined, preventing division by zero errors.

Input number is 1

How to Handle:

Return (1,1) since 1 is the only divisor and it is closest to itself.

Input number is a large perfect square

How to Handle:

The closest divisors would be the square root of the number with itself, which can be handled through typical iteration.

Input number is very large (close to integer limit)

How to Handle:

Ensure the multiplication of factors doesn't lead to integer overflow by using a larger data type or careful checks.

Input number is a prime number

How to Handle:

The only divisors are 1 and the number itself, handled correctly by the iteration to find divisors.

Input number is negative

How to Handle:

Return null or throw an exception since this problem typically deals with positive integers.

Number has multiple divisor pairs with the same minimal difference

How to Handle:

Return the first encountered pair or define a clear tie-breaking criteria such as returning the pair with the smaller first element.

Floating-point precision issues (if square root is used)

How to Handle:

Avoid relying on exact equality checks when comparing floating-point numbers from square root calculations; use a tolerance.