Four Divisors solution and explanation
Google
9 more videos on this problem
Four Divisors | Simplest Explanation | Dry Run | Straight Forward | Leetcode 1390 | codestorywithMIKcodestorywithMIK · 22:35 · 9K views
Four Divisors (Leetcode 1390)Coding Interviews · 8:44 · 2K views
1390. Four Divisors | Leetcode Daily - PythonLeetcode Daily · 8:43 · 1K views
Daily Leetcode #2105: Jan 04, 2026 - 1390. Four DivisorsProgramming Live with Larry · 5:44 · 566 views
Four Divisors | LeetCode 1390 | Java Code | Developer CoderDeveloper Coder · 12:25 · 363 views
Four Divisors | LeetCode 1390 - Pythonimpoldev · 7:18 · 248 views
Four Divisors | LeetCode 1390 | MathcodeTips · 9:22 · 231 views
1390. Four Divisors LeetCodeTechBase · 6:43 · 181 views
Four Divisors - Leetcode 1390 - PythonTim Huang · 4:49 · 123 views
Leetcode 1390 Four Divisors TutorialAmericanPy · 3:53 · 93 views
The problem
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 <= 1041 <= 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.
def sumFourDivisors(nums):
total_sum = 0
for num in nums:
sum_div = 0
count = 0
for i in range(1, num + 1):
if num % i == 0:
sum_div += i
count += 1
if count == 4:
total_sum += sum_div
return total_sum
print(sumFourDivisors([21, 4, 7]))public class Solution {
public int sumFourDivisors(int[] nums) {
int totalSum = 0;
for(int num : nums) {
int sum = 0, count = 0;
for(int i = 1; i <= num; i++) {
if(num % i == 0) {
sum += i;
count++;
}
}
if(count == 4) {
totalSum += sum;
}
}
return totalSum;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {21, 4, 7};
System.out.println(sol.sumFourDivisors(nums));
}
}#include <iostream>
#include <vector>
using namespace std;
int sumFourDivisors(vector<int>& nums) {
int totalSum = 0;
for(auto& num : nums) {
int sum = 0, count = 0;
for(int i = 1; i <= num; i++) {
if(num % i == 0) {
sum += i;
count++;
}
}
if(count == 4) {
totalSum += sum;
}
}
return totalSum;
}
int main() {
vector<int> nums = {21, 4, 7};
cout << sumFourDivisors(nums) << endl;
return 0;
}function sumFourDivisors(nums) {
let totalSum = 0;
for (let num of nums) {
let sum = 0, count = 0;
for (let i = 1; i <= num; i++) {
if (num % i === 0) {
sum += i;
count++;
}
}
if (count === 4) {
totalSum += sum;
}
}
return totalSum;
}
console.log(sumFourDivisors([21, 4, 7]));#include <stdio.h>
int sumFourDivisors(int* nums, int numsSize) {
int totalSum = 0;
for(int i = 0; i < numsSize; i++) {
int sum = 0, count = 0;
for(int j = 1; j <= nums[i]; j++) {
if(nums[i] % j == 0) {
sum += j;
count++;
}
}
if(count == 4) {
totalSum += sum;
}
}
return totalSum;
}
int main() {
int nums[] = {21, 4, 7};
int size = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", sumFourDivisors(nums, size));
return 0;
}using System;
class Program {
public static int SumFourDivisors(int[] nums) {
int totalSum = 0;
foreach(int num in nums) {
int sum = 0, count = 0;
for(int i = 1; i <= num; i++) {
if(num % i == 0) {
sum += i;
count++;
}
}
if(count == 4) {
totalSum += sum;
}
}
return totalSum;
}
static void Main() {
int[] nums = {21, 4, 7};
Console.WriteLine(SumFourDivisors(nums));
}
}This Python function iterates through each number in the input list, counting and summing divisors using nested loops. If exactly four divisors are found for a number, they're added to the total result.
Time Complexity: O(n * m).
Space Complexity: O(1).
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.
import math
def sumFourDivisors(nums):
total_sum = 0
for num in nums:
sum_div = 0
count = 0
for i in range(1, int(math.sqrt(num)) + 1):
if num % i == 0:
if i != num // i:
sum_div += i + num // i
count += 2
else:
sum_div += i
count += 1
if count == 4:
total_sum += sum_div
return total_sum
print(sumFourDivisors([21, 4, 7]))public class Solution {
public int sumFourDivisors(int[] nums) {
int totalSum = 0;
for(int num : nums) {
int sum = 0, count = 0;
for(int i = 1; i <= Math.sqrt(num); i++) {
if(num % i == 0) {
if(i != num / i) {
sum += i + num / i;
count += 2;
} else {
sum += i;
count++;
}
}
}
if(count == 4) {
totalSum += sum;
}
}
return totalSum;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {21, 4, 7};
System.out.println(sol.sumFourDivisors(nums));
}
}#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int sumFourDivisors(vector<int>& nums) {
int totalSum = 0;
for(auto& num : nums) {
int sum = 0, count = 0;
for(int i = 1; i <= sqrt(num); i++) {
if(num % i == 0) {
if(i != num / i) {
sum += i + num / i;
count += 2;
} else {
sum += i;
count++;
}
}
}
if(count == 4) {
totalSum += sum;
}
}
return totalSum;
}
int main() {
vector<int> nums = {21, 4, 7};
cout << sumFourDivisors(nums) << endl;
return 0;
}function sumFourDivisors(nums) {
let totalSum = 0;
for (let num of nums) {
let sum = 0, count = 0;
for (let i = 1; i <= Math.sqrt(num); i++) {
if (num % i === 0) {
if (i !== num / i) {
sum += i + num / i;
count += 2;
} else {
sum += i;
count++;
}
}
}
if (count === 4) {
totalSum += sum;
}
}
return totalSum;
}
console.log(sumFourDivisors([21, 4, 7]));#include <stdio.h>
#include <math.h>
int sumFourDivisors(int* nums, int numsSize) {
int totalSum = 0;
for(int i = 0; i < numsSize; i++) {
int n = nums[i], sum = 0, count = 0;
for(int j = 1; j <= sqrt(n); j++) {
if(n % j == 0) {
if(j != n / j) {
sum += j + n / j;
count += 2;
} else {
sum += j;
count++;
}
}
}
if(count == 4) {
totalSum += sum;
}
}
return totalSum;
}
int main() {
int nums[] = {21, 4, 7};
int size = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", sumFourDivisors(nums, size));
return 0;
}using System;
class Program {
public static int SumFourDivisors(int[] nums) {
int totalSum = 0;
foreach(int num in nums) {
int sum = 0, count = 0;
for(int i = 1; i <= Math.Sqrt(num); i++) {
if(num % i == 0) {
if(i != num / i) {
sum += i + num / i;
count += 2;
} else {
sum += i;
count++;
}
}
}
if(count == 4) {
totalSum += sum;
}
}
return totalSum;
}
static void Main() {
int[] nums = {21, 4, 7};
Console.WriteLine(SumFourDivisors(nums));
}
}The Python solution leverages mathematical functions to iterate only till the square root of each number, counting pairs of divisors and their sums. This cuts unnecessary calculations for efficiency.
Time Complexity: O(n * √m).
Space Complexity: O(1).
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).
function sumFourDivisors(nums: number[]): number {
const f = (x: number): number => {
let cnt = 2;
let s = x + 1;
for (let i = 2; i * i <= x; ++i) {
if (x % i === 0) {
++cnt;
s += i;
if (i * i !== x) {
++cnt;
s += Math.floor(x / i);
}
}
}
return cnt === 4 ? s : 0;
};
return nums.reduce((acc, x) => acc + f(x), 0);
}func sumFourDivisors(nums []int) (ans int) {
f := func(x int) int {
cnt, s := 2, x+1
for i := 2; i <= x/i; i++ {
if x%i == 0 {
cnt++
s += i
if i*i != x {
cnt++
s += x / i
}
}
}
if cnt == 4 {
return s
}
return 0
}
for _, x := range nums {
ans += f(x)
}
return
}impl Solution {
pub fn sum_four_divisors(nums: Vec<i32>) -> i32 {
let f = |x: i32| -> i32 {
let mut cnt = 2;
let mut s = x + 1;
let mut i = 2;
while i <= x / i {
if x % i == 0 {
cnt += 1;
s += i;
if i * i != x {
cnt += 1;
s += x / i;
}
}
i += 1;
}
if cnt == 4 { s } else { 0 }
};
let mut ans = 0;
for x in nums {
ans += f(x);
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Naive Divisor Counting | Time Complexity: O(n * m). |
| Optimized Divisor Checking | Time Complexity: O(n * √m). |
| Factor Decomposition | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Divisor Counting | O(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 |
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.