Skip to main content
Talentd

Four Divisors - Solution & Explanation

MediumArrayMath15 min readAsked at: Amazon, Microsoft, Meta +3
Practice this problem

Problem Statement

Given an integer array nums, return the sum of divisors of the integers in that array that have exactly four divisors. If there is no such integer in the array, return 0.

 

Example 1:

Input: nums = [21,4,7]
Output: 32
Explanation: 
21 has 4 divisors: 1, 3, 7, 21
4 has 3 divisors: 1, 2, 4
7 has 2 divisors: 1, 7
The answer is the sum of divisors of 21 only.

Example 2:

Input: nums = [21,21]
Output: 64

Example 3:

Input: nums = [1,2,3,4,5]
Output: 0

 

Constraints:

  • 1 <= nums.length <= 104
  • 1 <= nums[i] <= 105

Approach Overview

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.

Approach 1: Naive Divisor Counting

This approach involves iterating over each integer in the input array nums. For each integer, we count its divisors by checking every number from 1 up to the integer itself. If a number has exactly four divisors, we add the sum of these divisors to our total sum.

This C code defines a function sumFourDivisors that iterates over each integer in the given array. For each integer, it calculates the number and sum of its divisors. If exactly four divisors are found, their sum is added to the final result.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * m), where n is the length of the input array and m is the maximum integer value in the array (at most 100,000).
Space Complexity: O(1), as no extra space is used beyond primitive variables.

Try this approach in the editor →

Approach 2: Optimized Divisor Checking

This solution optimizes the divisor counting by iterating only up to the square root of each number. This reduces redundant calculations since divisors come in pairs. When exactly four divisors are found, their sum is included in the result.

This C implementation checks divisors up to the square root of each number, leveraging divisor pairs to minimize redundant calculations. This optimized approach efficiently determines and sums exactly four divisors if they exist.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * √m), reducing each number's divisor checks to its square root.
Space Complexity: O(1).

Try this approach in the editor →

Approach 3: Factor Decomposition

We can perform factor decomposition on each number. If the number of factors is 4, then this number meets the requirements of the problem, and we can add its factors to the answer.

The time complexity is O(n times \sqrt{n}), where n is the length of the array. The space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Naive Divisor Counting

Time Complexity: O(n * m), where n is the length of the input array and m is the maximum integer value in the array (at most 100,000).
Space Complexity: O(1), as no extra space is used beyond primitive variables.

Optimized Divisor Checking

Time Complexity: O(n * √m), reducing each number's divisor checks to its square root.
Space Complexity: O(1).

Factor Decomposition—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Naive Divisor CountingO(n * √m)O(1)Simple implementation when constraints are small or clarity matters more than pruning
Optimized Divisor Checking (Early Stop)O(n * √m)O(1)Preferred in interviews; stops scanning once divisor count exceeds four

Video Solution

Four Divisors | Simplest Explanation | Dry Run | Straight Forward | Leetcode 1390 | codestorywithMIK • codestorywithMIK • 9,063 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Four Divisors easy or hard?
Four Divisors is rated Medium because it requires recognizing divisor pair symmetry and limiting checks to √n. The coding itself is straightforward, but candidates must optimize the divisor search and handle edge cases like perfect squares correctly.
Four Divisors Python/Java solution
Both Python and Java implementations iterate through each number and check divisibility up to its square root. When a divisor pair is found, the algorithm updates the divisor count and sum, stopping early if the count exceeds four. The same logic translates directly to C++, JavaScript, and other languages.
How to solve Four Divisors in O(n)?
A strict O(n) solution is not typical without preprocessing. Most implementations check divisors up to √n for each number. With advanced preprocessing such as a sieve to identify primes and factorization patterns, you can reduce repeated work, but the standard accepted solution remains O(n * √m).
What is the best approach for Four Divisors?
The optimized divisor checking approach is the most practical. For each number, iterate only up to √n, count divisor pairs, and stop early once the count exceeds four. This avoids unnecessary checks for numbers that clearly have more than four divisors while keeping space usage constant.
Is Four Divisors asked at Google/Amazon/Meta?
Four Divisors is a medium-level problem commonly used in technical interview practice. Variants involving divisor counting and number properties appear in interviews at companies like Amazon and Google, especially when testing math reasoning and efficient iteration.
What data structure is used in Four Divisors?
The solution mainly relies on array traversal and mathematical divisor checks. No complex data structure is required. A few integer counters and accumulators track the number of divisors and their sum while scanning each value.
What is the time complexity of Four Divisors?
The typical solution runs in O(n * √m) time, where n is the number of elements in the array and m is the maximum value in the array. Each number requires checking potential divisors up to its square root. Space complexity remains O(1) because only counters and sums are stored.

Ready to solve this problem?

Practice Four Divisors with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays