Sum of Squares of Special Elements

Difficulty: Easy | Acceptance: 82.10% | Paid: No Topics: Array, Enumeration

You are given a 0-indexed integer array nums and a positive integer k.

We call an index i of nums special if i divides n, where n is the length of the array.

Return the sum of the squares of all special elements of nums.

• Examples
• Constraints
• Brute Force
• Optimized Enumeration

Examples

Example 1:

Input: nums = [1,2,3,4]
Output: 21
Explanation: Special elements are nums[0] = 1, nums[1] = 2, and nums[3] = 4.
Their squares are 1² = 1, 2² = 4, and 4² = 16.
The sum of squares is 1 + 4 + 16 = 21.

Example 2:

Input: nums = [2,7,1,19,18,3]
Output: 63
Explanation: Special elements are nums[0] = 2, nums[1] = 7, nums[2] = 1, and nums[5] = 3.
Their squares are 2² = 4, 7² = 49, 1² = 1, and 3² = 9.
The sum of squares is 4 + 49 + 1 + 9 = 63.

Constraints

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

Brute Force

Intuition Iterate through all indices from 1 to n, check if each index divides n, and accumulate the square of elements at special positions.

Steps

• Get the length n of the array
• Initialize total sum to 0
• Loop through indices 1 to n (1-indexed)
• If n is divisible by current index, add square of element at that index to total
• Return the total sum

class Solution:
    def sumOfSquares(self, nums: List[int]) -> int:
        n = len(nums)
        total = 0
        for i in range(1, n + 1):
            if n % i == 0:
                total += nums[i - 1] ** 2
        return total

Complexity

• Time: O(n)
• Space: O(1)
• Notes: Simple and straightforward approach suitable for the given constraints.

Optimized Enumeration

Intuition Instead of checking every index, directly find all divisors of n and only process those positions, reducing iterations to O(√n).

Steps

• Get the length n of the array
• Initialize total sum to 0
• Iterate from 1 to √n
• If i divides n, add square of element at index i-1
• If i ≠ n/i, also add square of element at index (n/i)-1
• Return the total sum

class Solution:
    def sumOfSquares(self, nums: List[int]) -> int:
        n = len(nums)
        total = 0
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                total += nums[i - 1] ** 2
                if i != n // i:
                    total += nums[n // i - 1] ** 2
        return total

Complexity

• Time: O(√n)
• Space: O(1)
• Notes: More efficient for larger n values, though both approaches work well within given constraints.