Four Divisors

Four Divisors

What is this problem about?

The Four Divisors interview question asks you to process an array of integers. For each integer, you must determine if it has exactly four distinct divisors. If it does, you add the sum of those four divisors to a running total. If it has any other number of divisors, it contributes 0 to the total.

Why is this asked in interviews?

Capital One uses this Math interview pattern problem to test your knowledge of Number Theory and optimization. A naive approach of checking every number up to $n$ to find divisors is $O(N)$, leading to $O(K \cdot N)$ overall, which is too slow. It evaluates if you know how to find divisors in $O(\sqrt{N})$ time and if you understand the mathematical properties of numbers with exactly four divisors.

Algorithmic pattern used

The problem is solved using Optimized Trial Division.

1. For each number num, iterate i from 1 to sqrt(num).
2. If num % i == 0, you found two divisors: i and num / i.
3. If i == num / i (a perfect square), that's only one distinct divisor.
4. Keep a count and a sum of divisors. If the count exceeds 4 during the loop, you can break early.
5. After the loop, if the count is exactly 4, add the sum to the total.

Example explanation

Array: [21, 4, 7]

1. 21: Divisors up to $\sqrt{21}$ (~4.5).
   • i = 1: divisors 1, 21. Count = 2, Sum = 22.
   • i = 2: no.
   • i = 3: divisors 3, 7. Count = 4, Sum = 22 + 10 = 32.
   • i = 4: no. Total divisors exactly 4. Add 32 to total.
2. 4: $\sqrt{4} = 2$.
   • i = 1: 1, 4. Count = 2.
   • i = 2: 2 (perfect square). Count = 3. Not exactly 4. Ignore.
3. 7: Divisors 1, 7. Count = 2. Ignore. Total Result: 32.

Common mistakes candidates make

• $O(N)$ Divisor Search: Iterating up to num instead of sqrt(num), resulting in a Time Limit Exceeded (TLE) error.
• Perfect Squares: Not handling the case where i == num / i, which incorrectly counts the square root twice.
• Not Breaking Early: Continuing to sum divisors even after finding 5 or 6, which wastes computation time.

Interview preparation tip

A number has exactly 4 divisors if it is the product of two distinct primes ($p \times q$) OR if it is the cube of a prime ($p^3$). While trial division is usually sufficient, knowing this property can sometimes lead to faster sieve-based solutions.