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

#programming #cpp #python #javascript

Finding the divisors of a number is a classic math problem that pops up frequently in competitive programming. This specific challenge asks us to filter a list of numbers based on a very strict mathematical property: having exactly four divisors.

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

To solve this efficiently, we need to understand how divisors work. A divisor is a number that divides another number without leaving a remainder. For example, the divisors of 6 are 1, 2, 3, and 6.

The provided C++ solution uses a Precomputation strategy. Instead of calculating the divisors for every number each time it appears in the input, we calculate the divisor count and the divisor sum for every possible number up to the maximum constraint () just once.

The Sieve Approach: We use a nested loop structure similar to the Sieve of Eratosthenes.
Outer Loop (): This represents a potential divisor.
Inner Loop (): This iterates through all multiples of . Since is a multiple of , we know that is a divisor of .
Counting and Summing: Every time we find a divisor for a number , we increment its count in divisor_num and add to its total in divisor_sum.

Once this table is built, answering the query for any number in the input array becomes a simple lookup.

Code Blocks

C++

#include <vector>
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 < MX; i++) {
        for (int j = i; j < MX; j += i) {
            divisor_num[j]++; 
            divisor_sum[j] += i;
        }
    }
    return 0;
}();

class Solution {
public:
    int sumFourDivisors(vector<int>& nums) {
        int ans = 0;
        for (int x : nums) {
            if (x < MX && divisor_num[x] == 4) {
                ans += divisor_sum[x];
            }
        }
        return ans;
    }
};

Python

# Precompute globally to share across multiple test cases
MX = 100001
divisor_num = [0] * MX
divisor_sum = [0] * MX

for i in range(1, MX):
    for j in range(i, MX, i):
        divisor_num[j] += 1
        divisor_sum[j] += i

class Solution:
    def sumFourDivisors(self, nums: list[int]) -> 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 logic
(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 dealing with multiple queries over a fixed range of values, calculating results beforehand saves significant time during execution.
The Sieve Pattern: Moving from a "check every number" mindset to a "mark every multiple" mindset changes complexity from to roughly .
Space-Time Tradeoff: We use extra memory (arrays of size ) to gain a massive boost in processing speed for the actual input array.

Final Thoughts

This problem is a fantastic introduction to how number theory is applied in software engineering. In the real world, these types of "sieve" techniques are foundational in cryptography, specifically in algorithms like RSA that rely heavily on the properties of divisors and prime factors. Understanding how to pre-process data can also be applied to search engines or caching systems, where speed is prioritized over memory.

DEV Community