algoadvance

Leetcode 1952. Three Divisors

Problem Statement

Leetcode Problem 1952: Three Divisors

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

Clarifying Questions

1. Q: What is the range of the input integer n? A: You can assume that n is a positive integer within the range [1, 10^4].

2. Q: Can n be a composite number? A: Yes, n can be any number within the given range, including prime and composite numbers.

3. Q: Should we handle negative numbers or zero? A: No, n is assumed to be a positive integer.

Strategy

To determine if a number n has exactly three divisors, we can make use of the following mathematical insight:

1. A number n has exactly three divisors if and only if it is the square of a prime number.

   • If n = p^2 where p is a prime number, the divisors of n will be: 1, p, and p^2.

Given this, we can follow these steps:

1. First, find the integer square root of n. Let’s call it sqrtN.
2. Check if sqrtN * sqrtN equals n. If not, n cannot have exactly three divisors.
3. Check if sqrtN is a prime number. If sqrtN is prime, then n has exactly three divisors.

Code

Here is the C++ implementation:

#include <cmath>

class Solution {
public:
    bool isThree(int n) {
        // Step 1: Calculate the integer square root of n
        int sqrtN = static_cast<int>(sqrt(n));
        
        // Step 2: Check if square of sqrtN equals n
        if (sqrtN * sqrtN != n) {
            return false;
        }
        
        // Step 3: Check if sqrtN is a prime number
        return isPrime(sqrtN);
    }
    
private:
    bool isPrime(int num) {
        if (num <= 1) return false;
        if (num == 2 || num == 3) return true;
        if (num % 2 == 0 || num % 3 == 0) return false;
        
        for (int i = 5; i * i <= num; i += 6) {
            if (num % i == 0 || num % (i + 2) == 0) {
                return false;
            }
        }
        
        return true;
    }
};

Time Complexity

• Step 1 (Finding the integer square root): This is a constant time operation, O(1) because sqrt is a mathematical function that operates in constant time.
• Step 2 (Checking if the square equals n): This is also a constant time operation, O(1).
• Step 3 (Checking if the number is prime): The time complexity of checking if a number is prime is O(sqrt(n)) because the loop runs up to sqrt(n).

So the overall time complexity is O(sqrt(n)). Given the constraints (n up to 10,000), this is efficient and should perform well within the given limits.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?