LeetCode 1952 - Three Divisors

The problem asks us to determine whether a given integer n has exactly three positive divisors. In other words, we want to check if there are precisely three distinct integers d such that n % d == 0 and d 0.

leetcodeeasymathenumerationnumber-theory

LeetCode Problem 1952

Difficulty: 🟢 Easy
Topics: Math, Enumeration, Number Theory

Solution

Problem Understanding

The problem asks us to determine whether a given integer n has exactly three positive divisors. In other words, we want to check if there are precisely three distinct integers d such that n % d == 0 and d > 0. For example, the number 4 has divisors 1, 2, and 4, which satisfies the condition, while 2 only has divisors 1 and 2, which does not.

The input is a single integer n constrained by 1 <= n <= 10^4, so it is relatively small. The output is a boolean value: true if n has exactly three divisors, false otherwise.

Key insights include realizing that a number with exactly three positive divisors must have the form p^2, where p is a prime number. This is because divisors of p^2 are 1, p, and p^2. If n is not a perfect square or its square root is not prime, then n cannot have exactly three divisors.

Important edge cases include n = 1, which only has one divisor, and perfect squares of composite numbers, such as n = 9 (3^2) or n = 16 (4^2). Only perfect squares of primes will satisfy the condition.

Approaches

A brute-force approach would enumerate all numbers from 1 to n and count how many divide n evenly. If the count reaches exactly three, we return true; otherwise, we return false. While this approach is simple and correct, it is inefficient for larger values of n because it checks divisibility for every integer up to n.

The key insight to an optimal solution is the property that any number with exactly three divisors must be the square of a prime. Therefore, the solution reduces to two checks: first, whether n is a perfect square, and second, whether its square root is prime. This is much faster because we only need to compute the integer square root and perform a primality check.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(1) Check each integer from 1 to n for divisibility and count divisors
Optimal O(√n) O(1) Check if n is a perfect square and verify if the square root is prime

Algorithm Walkthrough

  1. Compute the integer square root of n using a built-in square root function or integer exponentiation. This gives us a candidate sqrt_n such that sqrt_n * sqrt_n == n if n is a perfect square.
  2. If n is not a perfect square (i.e., sqrt_n * sqrt_n != n), return false immediately, since a number with exactly three divisors must be a perfect square.
  3. If n is a perfect square, we now need to check if sqrt_n is prime. A number is prime if it is greater than 1 and divisible only by 1 and itself.
  4. To check primality efficiently, iterate from 2 up to the square root of sqrt_n. If any number divides sqrt_n, it is not prime, and we return false.
  5. If no divisors are found in the loop, sqrt_n is prime, and thus n has exactly three divisors. Return true.

Why it works: The key invariant is that the only numbers with exactly three positive divisors are perfect squares of prime numbers. This is because divisors of p^2 are limited to 1, p, and p^2. Any other structure either produces fewer or more than three divisors.

Python Solution

import math

class Solution:
    def isThree(self, n: int) -> bool:
        sqrt_n = int(math.isqrt(n))
        if sqrt_n * sqrt_n != n:
            return False
        
        if sqrt_n < 2:
            return False
        
        for i in range(2, int(math.isqrt(sqrt_n)) + 1):
            if sqrt_n % i == 0:
                return False
        
        return True

The code first computes the integer square root of n to check for perfect-square status. If n is not a perfect square, the function immediately returns false. Next, it ensures that the square root is greater than 1, as 1 is not prime. Then, it iterates up to the square root of sqrt_n to check for divisibility. If any factor is found, sqrt_n is not prime, so n cannot have exactly three divisors. If no factors are found, the function returns true.

Go Solution

import "math"

func isThree(n int) bool {
    sqrtN := int(math.Sqrt(float64(n)))
    if sqrtN*sqrtN != n {
        return false
    }
    
    if sqrtN < 2 {
        return false
    }
    
    for i := 2; i*i <= sqrtN; i++ {
        if sqrtN % i == 0 {
            return false
        }
    }
    
    return true
}

In Go, math.Sqrt returns a float64, so we cast it to an integer. The integer square root check ensures that n is a perfect square. The loop checks for primality by testing divisors up to the integer square root of sqrtN. Otherwise, the logic mirrors the Python solution.

Worked Examples

Example 1: n = 2

  1. Compute sqrt_n = int(sqrt(2)) = 1.
  2. Check sqrt_n * sqrt_n == n: 1*1 != 2, so return false.

Example 2: n = 4

  1. Compute sqrt_n = int(sqrt(4)) = 2.
  2. Check sqrt_n * sqrt_n == n: 2*2 == 4, proceed.
  3. Check if sqrt_n is prime. 2 is prime, so return true.

Complexity Analysis

Measure Complexity Explanation
Time O(√n) We compute the square root and check for divisibility up to √(sqrt(n)) for primality
Space O(1) Only constant extra variables are used

The optimal solution reduces the problem size dramatically compared to brute-force by leveraging number theory properties, so even the worst-case check is efficient for n <= 10^4.

Test Cases

# Provided examples
assert Solution().isThree(2) == False  # 2 has only two divisors
assert Solution().isThree(4) == True   # 4 = 2^2, prime square

# Boundary values
assert Solution().isThree(1) == False  # 1 has only one divisor
assert Solution().isThree(9) == True   # 9 = 3^2, prime square
assert Solution().isThree(16) == False # 16 = 4^2, 4 is not prime

# Larger primes and non-primes
assert Solution().isThree(49) == True  # 7^2, 7 is prime
assert Solution().isThree(100) == False # 10^2, 10 is not prime
Test Why
n = 2 Smallest prime number, only two divisors
n = 4 Smallest perfect square of a prime
n = 1 Edge case, only one divisor
n = 9 Perfect square of prime 3
n = 16 Perfect square of non-prime 4
n = 49 Larger prime square 7^2
n = 100 Perfect square of composite 10

Edge Cases

The first important edge case is n = 1. Since 1 only has a single divisor, any naive approach that counts divisors may incorrectly assume it has three divisors. The implementation explicitly handles n = 1 by checking the square root and prime conditions.

The second edge case is perfect squares of non-primes, such as n = 16 (4^2). A naive check for perfect squares would return true incorrectly if we do not validate that the square root is prime. Our algorithm handles this by performing a prime check on the square root.

The third edge case is large prime squares near the upper limit, such as n = 10_000. We need to ensure that the integer square root calculation and primality check are efficient. The algorithm only iterates up to √(sqrt(n)), which is small even for the maximum input, making it robust against performance issues.