Jobs

Interviews

Discussions

Three Divisors

Easy

Microsoft

0 views

Given an integer n, return true if n has exactly three positive divisors. Otherwise, return false.

An integer m is a divisor of n if there exists an integer k such that n = k * m.

Example 1:

Input: n = 2
Output: false
Explantion: 2 has only two divisors: 1 and 2.

Example 2:

Input: n = 4
Output: true
Explantion: 4 has three divisors: 1, 2, and 4.

Constraints:

1 <= n <= 10⁴

Three Divisors

Easy

Microsoft

0 views

Given an integer n, return true if n has exactly three positive divisors. Otherwise, return false.

An integer m is a divisor of n if there exists an integer k such that n = k * m.

Example 1:

Input: n = 2
Output: false
Explantion: 2 has only two divisors: 1 and 2.

Example 2:

Input: n = 4
Output: true
Explantion: 4 has three divisors: 1, 2, and 4.

Constraints:

1 <= n <= 10⁴

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 possible values for the input integer n? Are there any specific constraints on its size?
Are we only considering positive divisors, or should I account for negative divisors as well?
Is n guaranteed to be a non-negative integer, or could it be negative, zero, or null?
If n is less than or equal to 1, what should the function return?
Are you expecting me to optimize for any particular edge cases or scenarios within the given constraints?

Brute Force Solution

Approach

To find if a number has exactly three divisors, we will check all the numbers smaller than it to see if they divide it evenly. We simply count how many divisors we find using this method.

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

Start with a counter for the number of divisors, initially set to zero.
Consider each number from 1 up to the input number.
For each of these numbers, check if it divides the input number without any remainder.
If a number divides the input number evenly, increase the divisor counter by one.
After checking all numbers up to the input number, see what the final divisor count is.
If the divisor count is exactly three, then the input number meets the requirement.
Otherwise, the input number does not have exactly three divisors.

Code Implementation

def has_three_divisors_brute_force(number):
    divisor_count = 0

    for possible_divisor in range(1, number + 1):
        # Check divisibility for each number
        if number % possible_divisor == 0:

            divisor_count += 1

    # Exactly three divisors indicate a square of a prime
    if divisor_count == 3:

        return True
    else:
        return False

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates from 1 up to the input number n. For each number in this range, it performs a single division operation to check if it's a divisor. Therefore, the number of division operations is directly proportional to the input n. Consequently, the time complexity is O(n).

Space Complexity

O(1) – The provided algorithm uses a fixed number of variables: a divisor counter and a loop variable that iterates from 1 to N. These variables consume a constant amount of memory, irrespective of the input number N. No additional data structures like arrays, lists, or hash maps are used to store intermediate results. Therefore, the auxiliary space complexity of the algorithm is constant.

Optimal Solution

Approach

The key insight is that a number has exactly three divisors if and only if it's the square of a prime number. Instead of checking all divisors, we'll focus on identifying if the given number is a perfect square of a prime.

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

First, find the square root of the number. If the square root is not a whole number, then the original number can't be the square of an integer, and thus it cannot have exactly three divisors, so we can immediately say 'no'.
Next, if the square root is a whole number, check if that square root is a prime number.
To check if the square root is prime, try dividing it by all numbers from 2 up to the square root of the square root. If none of these numbers divide it evenly, then the square root is prime.
If the square root is confirmed to be a prime number, then the original number is the square of a prime, meaning it has exactly three divisors, so the answer is 'yes'.
Otherwise, if the square root is not a prime number, the original number doesn't have exactly three divisors, and the answer is 'no'.

Code Implementation

def three_divisors(number_to_check):
    square_root = number_to_check**0.5

    # If not a perfect square, it can't be square of an int.
    if square_root != int(square_root):
        return False

    square_root = int(square_root)

    # Need to verify if the square root is a prime number
    for i in range(2, int(square_root**0.5) + 1):
        if square_root % i == 0:
            return False

    # 2 is a prime number, ensure it handles edge case
    if square_root <= 1:
        return False

    return True

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(sqrt(sqrt(n))) – First, we calculate the square root of the input number n, which takes O(1) time. Then, we check if the square root (sqrt(n)) is a prime number. Primality testing involves iterating from 2 up to the square root of sqrt(n). Thus, the primality test's complexity is O(sqrt(sqrt(n))). All other operations are constant time. Therefore, the overall time complexity is dominated by the primality test, resulting in O(sqrt(sqrt(n))).

Space Complexity

O(1) – The algorithm uses a constant amount of extra space. It calculates the square root of the input number, stores it in a variable, and then checks for primality using divisions. The variables used for calculations and the potential square root value occupy a fixed amount of memory, irrespective of the input number N. Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
n is less than 1	Return false because numbers less than 1 cannot have divisors in the positive domain.
n is 1	Return false because 1 only has one divisor (itself).
n is a prime number	Return false because a prime number has exactly two divisors: 1 and itself.
n is a perfect square of a prime number (e.g., 4, 9, 25)	Return true since a perfect square of a prime number has exactly three divisors (1, the prime number, and the number itself).
n is a large number (e.g., close to the maximum integer value)	Ensure that the loop calculating divisors doesn't cause integer overflow; consider using long or long long if necessary.
n is a composite number that is not a perfect square of a prime (e.g., 6, 8, 10)	Return false since these numbers will have more than three divisors.
Integer overflow during divisor calculation for very large n	Use appropriate data types (long or long long) to prevent overflow when calculating divisors.
Efficiency for very large n - can we optimize?	Optimize by only iterating up to the square root of n when finding divisors.

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 possible values for the input integer n? Are there any specific constraints on its size?
Are we only considering positive divisors, or should I account for negative divisors as well?
Is n guaranteed to be a non-negative integer, or could it be negative, zero, or null?
If n is less than or equal to 1, what should the function return?
Are you expecting me to optimize for any particular edge cases or scenarios within the given constraints?

Brute Force Solution

Approach

To find if a number has exactly three divisors, we will check all the numbers smaller than it to see if they divide it evenly. We simply count how many divisors we find using this method.

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

Start with a counter for the number of divisors, initially set to zero.
Consider each number from 1 up to the input number.
For each of these numbers, check if it divides the input number without any remainder.
If a number divides the input number evenly, increase the divisor counter by one.
After checking all numbers up to the input number, see what the final divisor count is.
If the divisor count is exactly three, then the input number meets the requirement.
Otherwise, the input number does not have exactly three divisors.

Code Implementation

def has_three_divisors_brute_force(number):
    divisor_count = 0

    for possible_divisor in range(1, number + 1):
        # Check divisibility for each number
        if number % possible_divisor == 0:

            divisor_count += 1

    # Exactly three divisors indicate a square of a prime
    if divisor_count == 3:

        return True
    else:
        return False

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, find the square root of the number. If the square root is not a whole number, then the original number can't be the square of an integer, and thus it cannot have exactly three divisors, so we can immediately say 'no'.
Next, if the square root is a whole number, check if that square root is a prime number.
To check if the square root is prime, try dividing it by all numbers from 2 up to the square root of the square root. If none of these numbers divide it evenly, then the square root is prime.
If the square root is confirmed to be a prime number, then the original number is the square of a prime, meaning it has exactly three divisors, so the answer is 'yes'.
Otherwise, if the square root is not a prime number, the original number doesn't have exactly three divisors, and the answer is 'no'.

Code Implementation

def three_divisors(number_to_check):
    square_root = number_to_check**0.5

    # If not a perfect square, it can't be square of an int.
    if square_root != int(square_root):
        return False

    square_root = int(square_root)

    # Need to verify if the square root is a prime number
    for i in range(2, int(square_root**0.5) + 1):
        if square_root % i == 0:
            return False

    # 2 is a prime number, ensure it handles edge case
    if square_root <= 1:
        return False

    return True

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
n is less than 1	Return false because numbers less than 1 cannot have divisors in the positive domain.
n is 1	Return false because 1 only has one divisor (itself).
n is a prime number	Return false because a prime number has exactly two divisors: 1 and itself.
n is a perfect square of a prime number (e.g., 4, 9, 25)	Return true since a perfect square of a prime number has exactly three divisors (1, the prime number, and the number itself).
n is a large number (e.g., close to the maximum integer value)	Ensure that the loop calculating divisors doesn't cause integer overflow; consider using long or long long if necessary.
n is a composite number that is not a perfect square of a prime (e.g., 6, 8, 10)	Return false since these numbers will have more than three divisors.
Integer overflow during divisor calculation for very large n	Use appropriate data types (long or long long) to prevent overflow when calculating divisors.
Efficiency for very large n - can we optimize?	Optimize by only iterating up to the square root of n when finding divisors.