How do you solve Three Divisors on LeetCode?

Three Divisors (LeetCode #1952) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(sqrt(n)) time complexity and O(1) space complexity. Key insight: A number has exactly three divisors if it is the square of a prime number.

What is the brute force solution for Three Divisors?

The brute force approach for Three Divisors is Brute Force, with O(n) time complexity and O(1) space complexity. To determine if a number has exactly three positive divisors, we can check all numbers from 1 to n to see if they divide n evenly. This is a straightforward approach but can be inefficient for larger numbers. The optimal Optimal Solution approach improves this to O(sqrt(n)).

What algorithm or data structure is used to solve Three Divisors?

Three Divisors uses the following concepts: Math, Enumeration, Number Theory. The recommended patterns to study are: Primality Testing, Mathematical Properties.

What are the interview tips for Three Divisors?

Always clarify the problem constraints before jumping into coding. Think about edge cases, such as small values of n. Explain your thought process clearly as you code.

What are common mistakes when solving Three Divisors?

Not considering the case when n is less than 4. Confusing the number of divisors with the properties of prime numbers.

#1952

Three Divisors

Easy

MathEnumerationNumber TheoryPrimality TestingMathematical Properties

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n)	O(sqrt(n))
Space	O(1)	O(1)

💡

Intuition

Time O(sqrt(n))Space O(1)

A number has exactly three positive divisors if and only if it is the square of a prime number. This is because the divisors of p^2 (where p is prime) are 1, p, and p^2.

⚙️

Algorithm

4 steps

1Step 1: Check if n is less than 4. If yes, return false.
2Step 2: Find the integer square root of n (let's call it sqrt_n).
3Step 3: Check if sqrt_n is a prime number.
4Step 4: If sqrt_n is prime, return true; otherwise, return false.

solution.py16 lines

1# Full working Python code
2import math
3
4def is_prime(num):
5    if num < 2:
6        return False
7    for i in range(2, int(math.sqrt(num)) + 1):
8        if num % i == 0:
9            return False
10    return True
11
12def hasThreeDivisors(n):
13    if n < 4:
14        return False
15    sqrt_n = int(math.sqrt(n))
16    return is_prime(sqrt_n)

ℹ

Complexity note: The time complexity is O(sqrt(n)) because we only check up to the square root of n to determine if it is prime. The space complexity is O(1) since we are using a constant amount of space.

1A number has exactly three divisors if it is the square of a prime number.
2Checking for primality is essential for the optimal solution.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.