Sum of Squares of Special Elements - Solution & Explanation

Problem Overview: Given an array nums of length n, an element is considered special if its 1-indexed position i divides n (i.e., n % i == 0). The task is to square each special element and return the total sum.

Approach 1: Iterating Through Divisors (O(sqrt(n)) time, O(1) space)

The key observation: instead of scanning every index, only positions that divide n can contribute to the result. Iterate through all divisors of n up to sqrt(n). For each divisor d, both d and n/d are valid positions in the array. Convert them to 0-based indices and add the square of the corresponding values. Handle the case where d == n/d to avoid double counting. This reduces unnecessary checks and focuses only on valid positions. The method uses constant extra memory and leverages basic math and divisor enumeration logic.

Approach 2: Using List Comprehension or Direct Enumeration (O(n) time, O(1) extra space)

A straightforward solution iterates through every index from 1 to n. For each position, check if n % i == 0. If true, square nums[i-1] and add it to the running total. In Python or JavaScript, this can be expressed compactly using list comprehension or functional iteration. While slightly less efficient than divisor enumeration for very large arrays, the code is extremely readable and performs well within typical constraints. This approach fits naturally with problems focused on array traversal and simple enumeration.

Recommended for interviews: Start with the direct enumeration approach because it clearly demonstrates you understand the condition n % i == 0. Then mention the divisor-based optimization. Enumerating divisors of n shows stronger algorithmic thinking and reduces the checks from O(n) to O(sqrt(n)), which is the most efficient approach.