Introduction

In this blog post, we will explore how to solve the LeetCode problem "1952" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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 <= 104

Explanation

Here's the breakdown:

• Key Idea: A number has exactly three divisors if and only if it is the square of a prime number. This is because the divisors would be 1, the prime number itself, and its square.

• Prime Check Optimization: Efficiently determine if a number is prime by only checking divisibility up to the square root of the number.

• Square Root Check: Compute the integer square root of the input n and verify if squaring it yields the original number. If it does, then check if the square root is a prime number.

• Complexity:

  • Runtime: O(sqrt(n))
  • Space: O(1)

Code

    import math

def isThree(n: int) -> bool:
    """
    Given an integer n, return true if n has exactly three positive divisors.
    Otherwise, return false.
    """
    if n < 4:
        return False

    root = int(math.sqrt(n))
    if root * root != n:
        return False

    if root <= 1:
      return False

    for i in range(2, int(math.sqrt(root)) + 1):
        if root % i == 0:
            return False

    return True