🍀 Beginner-Friendly Guide 'Four Divisors' – LeetCode 1390 (C++, Python, JavaScript)

Source: Dev.to

Problem Summary

You’re given:

• An array of integers called nums.

Your goal:

• Identify every number in the array that has exactly four divisors.
• Calculate the sum of all divisors for those specific numbers and return the total sum.

Intuition

A divisor is a number that divides another number without leaving a remainder. For example, the divisors of 6 are 1, 2, 3, 6.

The solution uses precomputation: we calculate the divisor count and the divisor sum for every possible number up to the maximum constraint (100 000) once, then answer queries in O(1) per element.

The Sieve Approach

• Outer loop (i) – iterates over potential divisors.
• Inner loop (j) – iterates over all multiples of i. Since i divides j, we increment the divisor count for j and add i to its divisor sum.

After building these tables, checking whether a number has exactly four divisors and retrieving its divisor sum is a simple array lookup.

Code Blocks

C++

#include 
using namespace std;

constexpr int MX = 100001;
int divisor_num[MX];
int divisor_sum[MX];

// Precompute divisor counts and sums for all numbers up to 100,000
int init = [] {
    for (int i = 1; i & nums) {
        int ans = 0;
        for (int x : nums) {
            if (x  int:
        total_ans = 0
        for x in nums:
            if divisor_num[x] == 4:
                total_ans += divisor_sum[x]
        return total_ans

JavaScript

const MX = 100001;
const divisor_num = new Int32Array(MX);
const divisor_sum = new Int32Array(MX);

// Precompute using a self‑invoking function
(function() {
    for (let i = 1; i < MX; i++) {
        for (let j = i; j < MX; j += i) {
            divisor_num[j]++;
            divisor_sum[j] += i;
        }
    }
})();

/**
 * @param {number[]} nums
 * @return {number}
 */
var sumFourDivisors = function(nums) {
    let totalAns = 0;
    for (let x of nums) {
        if (divisor_num[x] === 4) {
            totalAns += divisor_sum[x];
        }
    }
    return totalAns;
};

Key Takeaways

• Precomputation: When multiple queries operate over a fixed range, calculating results beforehand saves significant runtime.
• Sieve Pattern: Switching from “check every number” to “mark every multiple” reduces complexity from O(N·√N) to roughly O(N log N).
• Space‑Time Tradeoff: Using extra memory (arrays of size ≈ 100 k) yields a massive speed boost for processing the input array.

Final Thoughts

This problem showcases how number‑theoretic techniques, such as sieve‑based precomputation, are applied in software engineering. Similar ideas underpin cryptographic algorithms (e.g., RSA) and are useful in domains like search engines or caching systems, where fast query responses are prioritized over modest memory usage.