LeetCode Entry

1390. Four Divisors

04.12.2025 medium 2025 kotlin rust

Sum of exactly four-divisors of each number

1390. Four Divisors medium blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1225

Problem TLDR

Sum of exactly four-divisors of each number #medium #math

Intuition

Brute-force divisors up to sqrt(n) for each number.

    // math problem
    // lets brute-force?
    // two is 1 and number itself; two others we should find
    //
    // strange case: [7286,18704,70773,8224,91675] 10932
    // 10932 = 8224 + 1 + a + b
    // a*b = 10932
    //
    // 10932 = 8224 + 1 + 10932/b + b
    //
    // divisors are uniq    for 4: 1 2 4, 2 is collapsed
    //
    // ok 27 minute looking for hints
    // ok they suggest brute-force O(nsqrt(n))
    //

Approach

• another way: pre-find all divisors for 1..max

Complexity

• Time complexity: \(O(nsqrt(n))\)

• Space complexity: \(O(1)\)

Code

// 33ms
    fun sumFourDivisors(n: IntArray) = n.sumOf { n ->
        var f = 0; var x = 1; var s = 1+n
        while (++x*x <= n) if (n%x==0) {++f;s += x+n/x}
        if (f==1&&--x*x<n) s else 0
    }

// 31ms
    pub fn sum_four_divisors(n: Vec<i32>) -> i32 {
        let m = *n.iter().max().unwrap() as usize;
        let (mut c, mut s, mut r) = (vec![0; m+1], vec![0;m+1], 0);
        for a in 1..=m { for v in (a..=m).step_by(a) {c[v]+=1; s[v]+=a as i32}}
        n.iter().map(|&n|if (c[n as usize]==4) {s[n as usize]}else{0}).sum::<i32>()
    }