Leetcode 1952: Three Divisors
Given an integer n, return true if n has exactly three distinct positive divisors. Otherwise, return false. A divisor of n is a positive integer that divides n without leaving a remainder.
Problem
Approach
Steps
Complexity
Input: You are given an integer n. Your task is to determine if n has exactly three positive divisors.
Example: n = 9
Constraints:
• 1 <= n <= 10^4
Output: Return true if n has exactly three divisors, otherwise return false.
Example: Output: true
Constraints:
• The output should be a boolean value indicating whether n has exactly three divisors.
Goal: The goal is to check if the given integer n has exactly three distinct divisors.
Steps:
• Step 1: Find all divisors of n by iterating through integers from 1 to sqrt(n).
• Step 2: Count the number of divisors.
• Step 3: If the count of divisors is exactly 3, return true; otherwise, return false.
Goal: The integer n should be between 1 and 10^4, inclusive.
Steps:
• 1 <= n <= 10^4
Assumptions:
• The input integer n will always be a valid integer within the specified range.
• Input: Input: n = 9
• Explanation: The divisors of 9 are 1, 3, and 9, so it has exactly 3 divisors. Therefore, the output is true.
• Input: Input: n = 10
• Explanation: The divisors of 10 are 1, 2, 5, and 10, so it has 4 divisors. Therefore, the output is false.
Approach: The approach is to check the divisors of the given number n and verify if there are exactly three distinct divisors.
Observations:
• The number of divisors of n depends on its prime factorization. For n to have exactly three divisors, n must be a square of a prime number.
• If n is a perfect square and its square root is prime, then n will have exactly three divisors: 1, the prime number, and n itself.
Steps:
• Step 1: Check if n is a perfect square.
• Step 2: If n is a perfect square, check if its square root is prime.
• Step 3: If the square root is prime, return true (n has exactly three divisors), otherwise return false.
Empty Inputs:
• n cannot be 0, as the problem constraints specify that 1 <= n.
Large Inputs:
• When n is large (up to 10^4), the approach should efficiently handle checking if n is a perfect square and if its square root is prime.
Special Values:
• For prime numbers, n will never have exactly three divisors, so the output should be false.
Constraints:
• Ensure that n is checked within the valid range of 1 to 10^4.
bool isThree(int n) {
int d = 2;
for (int i = 2; i < n && d <= 3; i += 1)
d += n % i == 0;
return d == 3;
}
1 : Function Definition
bool isThree(int n) {
The function is defined with a boolean return type, indicating it will return true if 'n' has exactly three divisors, and false otherwise.
2 : Variable Initialization
int d = 2;
The variable 'd' is initialized to 2, as we start by assuming that 'n' has at least two divisors: 1 and 'n' itself.
3 : Loop for Divisor Check
for (int i = 2; i < n && d <= 3; i += 1)
A loop starts from 2 and iterates until 'n' or until 'd' exceeds 3. The loop checks if there are additional divisors of 'n'.
4 : Divisor Check
d += n % i == 0;
For each iteration, the condition 'n % i == 0' checks if 'i' is a divisor of 'n'. If it is, 'd' is incremented by 1.
5 : Return Statement
return d == 3;
The function returns true if 'd' equals 3, meaning 'n' has exactly three divisors. Otherwise, it returns false.
Best Case: O(1)
Average Case: O(sqrt(n))
Worst Case: O(sqrt(n))
Description: The time complexity is O(sqrt(n)) due to checking if n is a perfect square and verifying the primality of sqrt(n).
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is O(1) as only a constant amount of space is required for storing intermediate results.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus