Scale Engineer

Three Divisors

Easy
#1779Time: `O(n)` - The loop runs `n` times, making the time complexity linear with respect to the input `n`.Space: `O(1)` - We only use a constant amount of extra space for the counter variable.
Patterns
MathEnumerationNumber Theory

Prompt

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

Approaches

3 approaches with complexity analysis and trade-offs.

This approach directly implements the definition of a divisor. We iterate through all numbers from 1 to n and count how many of them divide n evenly. If the final count is exactly 3, we return true; otherwise, we return false.

Algorithm

  • If n < 4, return false.
  • Initialize a counter divisors to 0.
  • Iterate with a variable i from 1 to n.
  • In each iteration, check if n is divisible by i.
  • If n % i == 0, increment divisors.
  • After the loop, return true if divisors is exactly 3, otherwise return false.

Walkthrough

The algorithm starts by initializing a counter for divisors to zero. A small optimization is to note that the smallest number with three divisors is 4, so any n < 4 can be immediately rejected. It then enters a loop that iterates from i = 1 up to the given number n. Inside the loop, it checks if i is a divisor of n using the modulo operator (n % i == 0). If i is a divisor, the counter is incremented. After the loop completes, the algorithm checks if the final count of divisors is equal to 3.

class Solution {    public boolean isThree(int n) {        if (n < 4) {            return false;        }        int divisors = 0;        for (int i = 1; i <= n; i++) {            if (n % i == 0) {                divisors++;            }        }        return divisors == 3;    }}

Complexity

Time

`O(n)` - The loop runs `n` times, making the time complexity linear with respect to the input `n`.

Space

`O(1)` - We only use a constant amount of extra space for the counter variable.

Trade-offs

Pros

  • Very simple to understand and implement directly from the problem definition.

Cons

  • Inefficient for large values of n due to the linear time complexity. It will be too slow if n is large, though it passes for the given constraints (n <= 10^4).

Solutions

class Solution {public  boolean isThree(int n) {    int cnt = 0;    for (int i = 2; i < n; i++) {      if (n % i == 0) {        ++cnt;      }    }    return cnt == 1;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem