LeetCode 2778 - Sum of Squares of Special Elements

This problem asks us to compute the sum of squares of certain elements in an array, specifically the special elements. The array nums is 1-indexed, meaning the first element is at index 1 (not 0).

leetcodeeasyarrayenumeration

LeetCode Problem 2778

Difficulty: 🟢 Easy
Topics: Array, Enumeration

Solution

Problem Understanding

This problem asks us to compute the sum of squares of certain elements in an array, specifically the special elements. The array nums is 1-indexed, meaning the first element is at index 1 (not 0). An element nums[i] is considered special if its 1-based index divides the length of the array n exactly. In other words, i is a divisor of n.

The input is a list of integers of length n where 1 <= n <= 50 and each integer is in the range 1 <= nums[i] <= 50. These constraints tell us the array is small, and brute-force solutions are feasible. The output is a single integer: the sum of the squares of all special elements.

Edge cases to note include arrays of length 1, arrays where all elements are special (like when n is prime), and arrays where no elements but the first and last are special (like n being a composite with few divisors).

Approaches

A brute-force approach would iterate through all indices from 1 to n, check if each index divides n, and if so, square the corresponding element and add it to a running total. This approach is simple and correct because it directly implements the definition of special elements.

The optimal approach is essentially the same here, because n is at most 50. The key observation is that checking divisibility and squaring an element is O(1), and the maximum number of elements we need to check is only n, so there is no need for further optimization. We can directly iterate from index 1 to n, check n % i == 0, and sum the squares.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(1) Iterate through indices 1..n, check divisibility, sum squares
Optimal O(n) O(1) Same as brute force because n is small and constraints allow direct computation

Algorithm Walkthrough

  1. Compute the length n of the input array nums.
  2. Initialize a variable total_sum to 0. This will accumulate the sum of squares.
  3. Iterate through indices i from 1 to n inclusive (since the array is 1-indexed).
  4. For each i, check if n % i == 0. If true, this index is special.
  5. Square nums[i-1] (convert to 0-indexed) and add it to total_sum.
  6. After finishing the loop, return total_sum as the final result.

Why it works: Each index i that divides n is guaranteed to be a special element by definition. Summing the squares of these elements and ignoring non-special indices produces the correct result. The loop iterates over all potential special indices, ensuring no element is missed.

Python Solution

from typing import List

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

The Python code first computes the array length n and initializes total_sum. It loops from 1 to n inclusive, checks if i divides n, and if so, adds the square of nums[i-1] to total_sum. Using i-1 correctly converts the 1-based index to Python's 0-based indexing. Finally, it returns the accumulated sum.

Go Solution

func sumOfSquares(nums []int) int {
    n := len(nums)
    totalSum := 0
    for i := 1; i <= n; i++ {
        if n % i == 0 {
            totalSum += nums[i-1] * nums[i-1]
        }
    }
    return totalSum
}

In Go, the implementation mirrors Python. The length is computed, and a running total is initialized. The loop iterates from 1 to n, checks divisibility, and adds the square of the 0-indexed element to totalSum. Go handles integers naturally, and the slice access nums[i-1] adjusts for 1-indexing.

Worked Examples

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

i n % i Special? nums[i-1]^2 total_sum
1 4 % 1 = 0 Yes 1^2 = 1 1
2 4 % 2 = 0 Yes 2^2 = 4 5
3 4 % 3 = 1 No - 5
4 4 % 4 = 0 Yes 4^2 = 16 21

Output: 21

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

i n % i Special? nums[i-1]^2 total_sum
1 6 % 1 = 0 Yes 2^2 = 4 4
2 6 % 2 = 0 Yes 7^2 = 49 53
3 6 % 3 = 0 Yes 1^2 = 1 54
4 6 % 4 = 2 No - 54
5 6 % 5 = 1 No - 54
6 6 % 6 = 0 Yes 3^2 = 9 63

Output: 63

Complexity Analysis

Measure Complexity Explanation
Time O(n) Iterate through all indices 1..n once, constant work per iteration
Space O(1) Only a single accumulator variable is used, no extra data structures

The algorithm is linear with respect to the array size. Given the constraints (n <= 50), this is extremely efficient.

Test Cases

# Provided examples
assert Solution().sumOfSquares([1,2,3,4]) == 21  # Example 1
assert Solution().sumOfSquares([2,7,1,19,18,3]) == 63  # Example 2

# Boundary tests
assert Solution().sumOfSquares([5]) == 25  # Single element, index 1 divides 1
assert Solution().sumOfSquares([1,1,1,1,1]) == 3  # Only indices 1 and 5 are special
assert Solution().sumOfSquares([10]*50) == 100*12  # n = 50, divisors: 1,2,5,10,25,50

# Random small arrays
assert Solution().sumOfSquares([3,6,2]) == 13  # indices 1 and 3 divide 3
assert Solution().sumOfSquares([1,2,3,4,5,6,7]) == 50  # indices 1 and 7 divide 7
Test Why
[1,2,3,4] Example 1, verifies correct sum calculation
[2,7,1,19,18,3] Example 2, checks multiple special indices
[5] Edge case with single element
[1,1,1,1,1] Edge case with repeated values and selective divisors
[10]*50 Large n, multiple divisors, checks for overflow and correct summation
[3,6,2] Small array with non-consecutive special indices
[1,2,3,4,5,6,7] Prime-length array, only first and last indices are special

Edge Cases

Edge Case 1: Single element array [x]. This is special because 1 divides 1. Our implementation handles it because the loop runs from 1 to n, so nums[0] is correctly squared.

Edge Case 2: Array of prime length, e.g., n = 7. Only indices 1 and 7 divide n, so most elements are ignored. The implementation correctly skips non-special indices via the n % i == 0 condition.

Edge Case 3: Maximum size array n = 50. Multiple divisors exist (1,2,5,10,25,50). Our loop still correctly identifies all special indices and sums their squares without exceeding integer limits, and the solution handles accumulation safely in both Python and Go.

This solution is robust across the full input domain.