2778. Sum of Squares of Special Elements

This problem is a favorite warm-up question at companies like Google because it tests your understanding of divisibility, array indexing, and the ability to translate mathematical conditions into clean code. At its core, this is a divisor identification problem disguised as an array traversal challenge.

Problem statement

You are given a 1-indexed integer array nums of length n. Your task is to return the sum of the squares of all special elements in nums.

An element nums[i] is considered special if its indexes i divides n evenly (i.e., n % i == 0).

Constraints:

• 1 <= nums.length == n <= 50
• 1 <= nums[i] <= 50

Examples

Intuition

The key approach to this problem is to iterate over all possible indexes from 1 to n, check whether each index divides n, and, if so, square the element at that index and add it to our running sum.

Step-by-step algorithm

1. Get the length of the array and store it as n.
2. Initialize a variable total_sum to 0 to store the cumulative sum of squares.
3. Iterate through each potential index i from 1 to n + 1.
   1. For each i, check if i is a divisor of n (i.e., n % i == 0 ).
      1. If i divides n, access the element at position i in the 1-indexed array (which is nums[i - 1] in 0-indexed Python, square this element and add it to total_sum.
4. After checking all indexes, return total_sum.

1 / 7

Code implementation

Let’s look at the code for the solution we just discussed.

def sumOfSquares(nums):
    n = len(nums)
    total_sum = 0
    
    # Iterate through all potential 1-indexed positions
    for i in range(1, n + 1):
        # Check if current index divides n evenly
        if n % i == 0:
            # Convert 1-indexed position to 0-indexed array access
            # Square the element and add to running sum
            total_sum += nums[i - 1] ** 2
    
    return total_sum


def main():
    """
    Driver function with diverse test cases
    """
    test_cases = [
        [1, 2, 3, 4],                    # n=4, divisors: 1,2,4
        [2, 7, 1, 19, 18, 3],           # n=6, divisors: 1,2,3,6
        [5],                             # n=1, only divisor: 1
        [10, 20, 30, 40, 50],           # n=5, divisors: 1,5 (prime length)
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]  # n=12, multiple divisors
    ]
    
    for i, nums in enumerate(test_cases, 1):
        result = sumOfSquares(nums)
        print(f"{i}\t Input:  nums = {nums}")
        print(f"  \t Output: {result}")
        print("-" * 75)

if __name__ == "__main__":
    main()

Time complexity

The time complexity of this algorithm is O(n) where n is the length of the input array. We iterate through all indexes from 1 to n exactly once, performing a constant-time modulo operation and array access for each index.

Space complexity

The space complexity is O(1) because we only use a fixed amount of extra space regardless of input size. We maintain only two variables: total_sum (to accumulate the result) and n (to store the array length). We don’t create any additional data structures that scale with the input, and the iteration variable i is reused in each loop iteration. In the worst case, where every index divides n (which only happens when n = 1), we still use constant space.

Common pitfalls and interview tips

1. Off-by-one indexing errors: The problem explicitly states the array is 1-indexed, but Python uses 0-indexing. Always remember to access nums[i - 1] when working with a 1-indexed position i. A common mistake is to access nums[i] directly, which will cause an index out of bounds error when i == n.
2. Forgetting that n itself is always a divisor: Every positive integer divides itself, so nums[n] (or nums[n - 1] in 0-indexed Python) will always be included in the sum. This is easy to miss during manual calculation, especially with larger arrays.
3. Misunderstanding the divisibility check: Some candidates mistakenly check if i % n == 0 instead of n % i == 0. Remember: we’re asking “does index i divide the length n?”, not the reverse. The condition must be n % i == 0.