Three Divisors — Solution in Python, Java & C++
Three Divisors solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem, asked at Amazon and TCS.
Three Divisors is an easy coding problem on math and number theory, asked in Amazon and TCS interviews.
- Difficulty: Easy
- Topics: Math, Number Theory
- Asked at: Amazon, TCS
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an integer n, return true if it has exactly three positive divisors, and false otherwise.
Example 1
Input: n = 2
Output: false
Explanation: Its divisors are 1 and 2.
Example 2
Input: n = 4
Output: true
Explanation: Its divisors are 1, 2 and 4.
Example 3
Input: n = 9
Output: true
Constraints
1 <= n <= 10000
Hints for Three Divisors
Hint 1
Counting divisors up to
sqrt(n)is enough — divisors come in pairs.Hint 2
Remember that a perfect square's square root pairs with itself and must be counted once.
Hint 3
Which numbers have exactly three divisors? Look at the answer's shape.
How to solve Three Divisors
Divisors pair up as d and n/d, so counting up to sqrt(n) covers them all. The characterisation, if you want it: exactly the squares of primes have three divisors.
Approach
- Loop
dfrom 1 whiled * d <= n. - When
ddividesn, add 2 to the count — or 1 whend * d == n, since the pair collapses. - Bail out early once the count exceeds 3.
- Return whether the final count is exactly 3.
Why it works
n = p² for prime p has divisors 1, p, p² — exactly three. Any other form has either fewer (1 or a prime) or more (a composite with two distinct prime factors, or a higher prime power).
Complexity
- Time —
O(sqrt(n)) - Space —
O(1)
Pitfalls
- Double-counting the square root turns 4 and 9 into four-divisor numbers.
- Looping all the way to
nis 10,000 iterations here — fine, but the sqrt bound is the right habit. n = 1has a single divisor and must returnfalse.
Reference solution
Python
def isThree(n: int) -> bool:
count = 0
d = 1
while d * d <= n:
if n % d == 0:
count += 1 if d * d == n else 2
if count > 3:
return False
d += 1
return count == 3Java
public static boolean isThree(int n) {
int count = 0;
for (int d = 1; d * d <= n; d++) {
if (n % d == 0) {
count += d * d == n ? 1 : 2;
if (count > 3) return false;
}
}
return count == 3;
}C++
bool isThree(int n) {
int count = 0;
for (int d = 1; d * d <= n; d++) {
if (n % d == 0) {
count += d * d == n ? 1 : 2;
if (count > 3) return false;
}
}
return count == 3;
}JavaScript
var isThree = function(n) {
let count = 0;
for (let d = 1; d * d <= n; d++) {
if (n % d === 0) {
count += d * d === n ? 1 : 2;
if (count > 3) return false;
}
}
return count === 3;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.