Four Divisors - Practice Coding Problems

Four Divisors - Problem

Array Math Medium

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.

Note: A number has exactly four divisors when it is either:

The cube of a prime number (p³)
The product of two distinct prime numbers (p × q)

Input & Output

Example 1 — Mixed Numbers

$ Input: nums = [21,4,7]

› Output: 32

💡 Note: 21 has divisors [1,3,7,21] (4 divisors, sum=32). 4 has divisors [1,2,4] (3 divisors). 7 has divisors [1,7] (2 divisors). Only 21 has exactly 4 divisors.

Example 2 — Multiple Valid Numbers

$ Input: nums = [21,21]

› Output: 64

💡 Note: Both instances of 21 have exactly 4 divisors [1,3,7,21] with sum 32. Total: 32 + 32 = 64.

Example 3 — No Valid Numbers

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

› Output: 0

💡 Note: 1 has 1 divisor, 2 has 2 divisors, 3 has 2 divisors, 4 has 3 divisors, 5 has 2 divisors. None have exactly 4 divisors.

Constraints

1 ≤ nums.length ≤ 10⁴
1 ≤ nums[i] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array of integers to check

Find 4-Divisor Numbers

Identify which have exactly 4 divisors

Sum Divisors

Add up all divisors of valid numbers

Key Takeaway

🎯 Key Insight: Only p³ and p×q (distinct primes) have exactly 4 divisors

Asked in

G Google 12 f Facebook 8 a Amazon 6

The key insight is that only numbers of the form p³ (prime cubed) or p×q (product of two distinct primes) have exactly 4 divisors. Best approach uses mathematical pattern recognition to identify these cases directly. Time: O(n × √max(nums)), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Optimized Divisor Counting	O(n × sqrt(max(nums)))	O(1)	Count divisors efficiently by checking only up to sqrt(n)
Mathematical Pattern Recognition	O(n × sqrt(max(nums)))	O(1)	Use mathematical properties to identify numbers with exactly 4 divisors
Brute Force Divisor Counting	O(n × max(nums))	O(1)	For each number, count all divisors by checking every number from 1 to n

Optimized Divisor Counting — Algorithm Steps

For each number in array
Check divisors from 1 to sqrt(n)
For each divisor i, add both i and n/i
Count total divisors and sum if exactly 4

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate √n

Find square root of number

Check 1 to √n

For divisor i, also get n/i

Count & Sum

If exactly 4, add sum to result

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int countAndSumDivisors(int n, int* sum) {
    if (n <= 0) {
        *sum = 0;
        return 0;
    }
    
    int divisors[1000];
    int count = 0;
    int sqrtN = sqrt(n);
    
    for (int i = 1; i <= sqrtN; i++) {
        if (n % i == 0) {
            divisors[count++] = i;
            if (i != n / i) {
                divisors[count++] = n / i;
            }
        }
    }
    
    *sum = 0;
    for (int i = 0; i < count; i++) {
        *sum += divisors[i];
    }
    return count;
}

int solution(int* nums, int numsSize) {
    int result = 0;
    for (int i = 0; i < numsSize; i++) {
        int divisorSum;
        int count = countAndSumDivisors(nums[i], &divisorSum);
        if (count == 4) {
            result += divisorSum;
        }
    }
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%d\n", solution(nums, numsSize));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × sqrt(max(nums)))

For each of n numbers, check up to sqrt(max(nums)) potential divisors

✓ Linear Growth

Space Complexity

O(1)

Only using variables for counting and summing

✓ Linear Space

12.5K Views

Medium Frequency

~25 min Avg. Time

428 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized Divisor Counting — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler