Problem Description

You are given an integer array nums that uses 1-based indexing (the first element is at index 1, not 0). The array has length n.

An element nums[i] is considered special if its index i divides the length n evenly. In other words, nums[i] is special when n % i == 0.

Your task is to find all the special elements in the array, square each of them, and return the sum of these squared values.

Example walkthrough:

• If nums = [1, 2, 3, 4] and n = 4
• Index 1: 4 % 1 == 0 ✓ (1 divides 4), so nums[1] = 1 is special
• Index 2: 4 % 2 == 0 ✓ (2 divides 4), so nums[2] = 2 is special
• Index 3: 4 % 3 != 0 ✗ (3 doesn't divide 4), so nums[3] = 3 is not special
• Index 4: 4 % 4 == 0 ✓ (4 divides 4), so nums[4] = 4 is special
• The special elements are 1, 2, and 4
• Return 1² + 2² + 4² = 1 + 4 + 16 = 21

The solution iterates through the array with 1-based indexing using enumerate(nums, 1), checks if each index divides n, and if so, includes the square of that element in the sum.

Intuition

The key insight is recognizing that we need to identify which positions in the array are divisors of the array's length. Since we're looking for indices i where n % i == 0, we're essentially finding all divisors of n that are also valid array indices (between 1 and n).

Think about it this way: if the array has length 6, the divisors of 6 are 1, 2, 3, and 6. These are exactly the positions we need to check. The elements at these positions are our "special" elements.

Once we identify these special positions, the problem becomes straightforward:

1. Check each index to see if it divides n
2. If it does, take the element at that position and square it
3. Add all these squared values together

The elegance of the solution comes from using Python's enumerate(nums, 1) which gives us 1-based indexing directly, avoiding any off-by-one errors. We can then use a generator expression to combine all three steps into a single line: check divisibility (n % i == 0), square the element (x * x), and sum everything up (sum(...)).

This approach is optimal because we only need one pass through the array, checking each position once, giving us O(n) time complexity with O(1) extra space.

Solution Approach

The implementation uses a single-pass iteration with a generator expression to efficiently compute the sum of squares of special elements.

Step-by-step walkthrough:

1. Get the array length: Store n = len(nums) to avoid repeated length calculations.

2. Iterate with 1-based indexing: Use enumerate(nums, 1) which returns pairs of (index, value) where:

   • i represents the 1-based index (starting from 1)
   • x represents the element value at that position

3. Check divisibility condition: For each position, evaluate n % i == 0 to determine if the current index divides the array length evenly.

4. Square and sum: When the condition is met, include x * x in the sum. The generator expression x * x for i, x in enumerate(nums, 1) if n % i == 0 produces the squares of all special elements.

5. Return the result: The sum() function aggregates all squared values into the final answer.

Example execution with nums = [1, 2, 3, 4]:

• n = 4
• Iteration 1: i=1, x=1 → 4 % 1 == 0 is True → include 1 * 1 = 1
• Iteration 2: i=2, x=2 → 4 % 2 == 0 is True → include 2 * 2 = 4
• Iteration 3: i=3, x=3 → 4 % 3 == 1 is False → skip
• Iteration 4: i=4, x=4 → 4 % 4 == 0 is True → include 4 * 4 = 16
• Final sum: 1 + 4 + 16 = 21

The solution leverages Python's generator expression for memory efficiency, as it computes values on-the-fly without creating intermediate lists.

Example Walkthrough

Let's walk through a concrete example with nums = [5, 1, 2, 7, 3, 9] where n = 6.

Step 1: Identify the array length

• n = len(nums) = 6

Step 2: Check each position to find special elements

We iterate through the array with 1-based indexing and check if each index divides 6:

• Position 1: nums[1] = 5

  • Check: 6 % 1 = 0 ✓ (1 divides 6)
  • This is special! Include 5² in our sum

• Position 2: nums[2] = 1

  • Check: 6 % 2 = 0 ✓ (2 divides 6)
  • This is special! Include 1² in our sum

• Position 3: nums[3] = 2

  • Check: 6 % 3 = 0 ✓ (3 divides 6)
  • This is special! Include 2² in our sum

• Position 4: nums[4] = 7

  • Check: 6 % 4 = 2 ✗ (4 doesn't divide 6 evenly)
  • Not special, skip this element

• Position 5: nums[5] = 3

  • Check: 6 % 5 = 1 ✗ (5 doesn't divide 6 evenly)
  • Not special, skip this element

• Position 6: nums[6] = 9

  • Check: 6 % 6 = 0 ✓ (6 divides 6)
  • This is special! Include 9² in our sum

Step 3: Calculate the sum of squares

• Special elements found: 5, 1, 2, and 9
• Sum of squares: 5² + 1² + 2² + 9² = 25 + 1 + 4 + 81 = 111

Implementation in code:

def sumOfSquares(nums):
    n = len(nums)
    return sum(x * x for i, x in enumerate(nums, 1) if n % i == 0)

The solution efficiently combines iteration, filtering, and calculation in a single pass through the array.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm iterates through the list once using enumerate(nums, 1), which takes O(n) time. For each element, it performs:

• An index check n % i == 0 which is O(1)
• A squaring operation x * x which is O(1)
• Adding to the sum which is O(1)

Since we perform constant-time operations for each of the n elements, the overall time complexity is O(n).

Space Complexity: O(1)

The algorithm uses a generator expression sum(x * x for i, x in enumerate(nums, 1) if n % i == 0) which evaluates lazily and doesn't create an intermediate list. It only maintains:

• The variable n to store the length
• The running sum accumulator inside the sum() function
• The iterator variables i and x

All of these use constant extra space regardless of input size, resulting in O(1) space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Confusing 0-based vs 1-based indexing

A frequent mistake is forgetting that the problem uses 1-based indexing and accidentally implementing the solution with standard 0-based indexing.

Incorrect approach:

# Wrong: Uses 0-based indexing
result = sum(num * num for i, num in enumerate(nums) if n % i == 0)

This will cause a ZeroDivisionError when i = 0 and miss the correct indices.

Correct approach:

# Correct: Uses 1-based indexing
result = sum(num * num for i, num in enumerate(nums, 1) if n % i == 0)

2. Using index instead of value for squaring

Another common error is squaring the index i instead of the element value num.

Incorrect approach:

# Wrong: Squares the index instead of the value
result = sum(i * i for i, num in enumerate(nums, 1) if n % i == 0)

Correct approach:

# Correct: Squares the element value
result = sum(num * num for i, num in enumerate(nums, 1) if n % i == 0)

3. Off-by-one errors with manual indexing

When using range-based iteration, developers might create off-by-one errors.

Incorrect approach:

# Wrong: Misses the last element
result = 0
for i in range(1, len(nums)):  # Should be range(1, len(nums) + 1)
    if n % i == 0:
        result += nums[i-1] ** 2

Correct approach:

# Correct: Includes all elements
result = 0
for i in range(1, len(nums) + 1):
    if n % i == 0:
        result += nums[i-1] ** 2

4. Inefficient repeated length calculations

While not incorrect, repeatedly calling len(nums) in loops reduces performance.

Inefficient approach:

result = sum(num * num for i, num in enumerate(nums, 1) if len(nums) % i == 0)

Efficient approach:

n = len(nums)
result = sum(num * num for i, num in enumerate(nums, 1) if n % i == 0)