Four Divisors - Video Solutions

Problem Overview: You receive an integer array nums. For each number, determine whether it has exactly four divisors. If it does, add the sum of those divisors to the final result. Return the total across all numbers.

Approach 1: Naive Divisor Counting (O(n * √m) time, O(1) space)

For every number in nums, iterate from 1 to √num and check whether the current value divides the number. When a divisor d is found, add both d and num / d to the divisor set (handling the square root case carefully). Count how many divisors appear and compute their sum. If the total divisor count equals exactly four, include the sum in the final answer. This approach directly simulates divisor enumeration using basic math operations and simple iteration over the array.

Approach 2: Optimized Divisor Checking (O(n * √m) time, O(1) space)

Instead of collecting every divisor, track the count while scanning up to √num. Each time a divisor is found, increment the count by two (for the pair d and num/d) and add them to the running sum. The key optimization: stop early once the divisor count exceeds four. Most numbers have more than four divisors, so early termination avoids unnecessary checks. For numbers that end with exactly four divisors, the accumulated sum is added to the result. This keeps memory constant while reducing wasted work during divisor scans.

Recommended for interviews: The optimized divisor checking approach is typically expected. Interviewers want to see that you limit the search to √num and prune early when the divisor count exceeds four. Showing the naive enumeration first demonstrates understanding of divisor properties, but the optimized version proves you can reduce unnecessary computation in real coding interviews.