algoadvance

Leetcode 1952. Three Divisors

Problem Statement

You are given an integer n, return true if n has exactly three positive divisors. Otherwise, return false.

An integer m has exactly three positive divisors if and only if there exist two integers a and b such that:

  1. a is a prime number.
  2. b = a^2 and b is exactly divisible by 1, a, and a^2.

Clarifying Questions

  1. What are the constraints on the integer n?
    • 1 <= n <= 10^4
  2. What should be returned if n is less than 2 or is not a perfect square?
    • If n is less than 4 (since (2^2=4)), return false.
    • If n is not a perfect square, return false.

Strategy

To solve the problem, we need to identify if n has exactly three divisors, which happens only when n is of the form ( p^2 ), where p is a prime. Here’s our plan:

  1. Check if n is a perfect square: Calculate the integer square root of n. If squaring it back doesn’t give n, then n is not a perfect square.
  2. Check if the square root is prime: If n is a perfect square, the next step is to check if the square root of n is a prime number.
  3. Return true if both conditions are met: If both conditions are fulfilled, and the number has exactly three divisors (1, the square root, and the number itself).

Code

public class ThreeDivisors {
    public boolean isThree(int n) {
        // Check if n is a perfect square
        int sqrt = (int) Math.sqrt(n);
        if (sqrt * sqrt != n) {
            return false;
        }

        // Check if sqrt is a prime number
        return isPrime(sqrt);
    }

    // Helper method to check if a number is prime
    private boolean isPrime(int num) {
        if (num <= 1) return false;
        if (num == 2) return true; // 2 is the only even prime number
        if (num % 2 == 0) return false; // Other even numbers are not primes

        for (int i = 3; i <= Math.sqrt(num); i += 2) {
            if (num % i == 0) return false;
        }
        return true;
    }
    
    // Main method to test the function
    public static void main(String[] args) {
        ThreeDivisors td = new ThreeDivisors();
        int test1 = 9;  // True, because 9 = 3^2 and 3 is prime
        int test2 = 12; // False, because 12 is not a square of a prime
        int test3 = 16; // False, because 16 = 4^2 and 4 is not prime
        
        System.out.println(td.isThree(test1)); // Expected: True
        System.out.println(td.isThree(test2)); // Expected: False
        System.out.println(td.isThree(test3)); // Expected: False
    }
}

Time Complexity

Thus, the overall time complexity is O(sqrt(n)). This is efficient given the constraints (1 <= n <= 10^4).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI