2778. Sum of Squares of Special Elements

EasyView on LeetCode

Array enumeration

Time: O(sqrt n)

Space: O(1)

Problem Overview

A 1-indexed position i is special when it divides n, the length of the array.

Intuition

A 1-indexed position i is special when it divides n, the length of the array. So the task is really to list the divisors of n and add up the squares of the values sitting there. Divisors come in pairs: whenever d divides n, so does n / d, and one of the two is at most the square root of n. Trying d only up to that square root finds both members of every pair, so the scan is far shorter than walking the whole array.

Algorithm

1Let n be the array length and start the answer at 0.
2Loop d from 1 while d times d is at most n.
3Skip d when n is not divisible by it.
4Otherwise add the square of nums[d - 1], converting the position to a 0-based index.
5Let pair be n / d. If pair is different from d, also add the square of nums[pair - 1].
6Return the answer once the loop ends.

Example Walkthrough

Input: nums = [2,7,1,19,18,3]

1.n is 6, so d runs over 1 and 2, because 3 times 3 is already larger than 6.
2.d = 1 divides 6 and pairs with 6, adding 2 squared and 3 squared for 4 + 9 = 13.
3.d = 2 divides 6 and pairs with 3, adding 7 squared and 1 squared for 49 + 1 = 50.
4.The special positions are 1, 2, 3, and 6, and the total is 13 + 50.

Output: 63

Common Pitfalls

•Positions are 1-indexed. Position d lives at index d - 1 in the array.
•When n is a perfect square, d and n / d are the same position. Count it only once.
•Checking every index against n works but takes linear time, while divisor pairs need only the square root of n steps.
•Write the loop bound as d * d <= n to avoid floating point square roots.

2778.cs

// Approach: The special positions (1-indexed) are exactly the divisors of n.
// Divisors come in pairs d and n / d with d <= sqrt(n), so trying d up to
// sqrt(n) finds every one. A perfect square divisor is counted only once.
// Time: O(sqrt n) Space: O(1)

public class Solution
{
    public int SumOfSquares(int[] nums)
    {
        int n = nums.Length;
        int ans = 0;
        for (int d = 1; d * d <= n; d++)
        {
            if (n % d != 0)
                continue;
            ans += nums[d - 1] * nums[d - 1];
            int pair = n / d;
            if (pair != d)
                ans += nums[pair - 1] * nums[pair - 1];
        }
        return ans;
    }
}

Was this solution helpful?