Is Three Divisors easy or hard?

Three Divisors is classified as an easy problem. The main challenge is recognizing the mathematical insight that only prime squares have exactly three divisors. Once that observation is made, the implementation becomes straightforward.

How to solve Three Divisors in O(n)?

A naive method could iterate from 1 to n and count divisors, which leads to O(n) time. This approach is inefficient because most checks are unnecessary. The optimized solution reduces work to O(sqrt(n)) by leveraging the fact that numbers with exactly three divisors must be prime squares.

What is the best approach for Three Divisors?

The best approach is checking whether n is a square of a prime number. Compute sqrt(n), verify that it is an integer, then check if the square root is prime. This works because only prime squares have exactly three divisors. The complexity is O(sqrt(n)) due to the primality check.

Is Three Divisors asked at Google/Amazon/Meta?

Three Divisors is a typical easy-level screening question used in coding interviews and online assessments. Variations involving divisor counts or prime properties appear at companies like Amazon, Google, and Microsoft to test basic number theory and reasoning skills.

What data structure is used in Three Divisors?

No special data structure is required. The problem relies on mathematical properties and simple arithmetic operations such as square root calculation and divisibility checks. It primarily tests number theory concepts rather than data structure usage.

What is the time complexity of Three Divisors?

The optimal solution runs in O(sqrt(n)) time and O(1) space. You compute the square root and check whether that value is prime using trial division up to sqrt(root). Brute divisor enumeration also takes O(sqrt(n)) but performs more unnecessary checks.

Three Divisors Python or Java solution approach?

Both Python and Java implementations follow the same logic: compute sqrt(n), check if n is a perfect square, then verify that the square root is prime using trial division up to sqrt(root). The algorithm runs in O(sqrt(n)) time and uses constant extra space.

Description Hints 2 Solution Video 8:20

1952. Three Divisors

Easy65.2% acceptance3 companies

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 <= 10⁴

Asked at 3 companies

Microsoft Bloomberg

Google

Topics

Hints open one at a time

Hint 1

You can count the number of divisors and just check that they are 3

Hint 2

Beware of the case of n equal 1 as some solutions might fail in it

8:20

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution