Skip to main content
Talentd

Sum of Squares of Special Elements - Solution & Explanation

EasyArrayEnumeration9 min readAsked at: Google
Practice this problem

Problem Statement

You are given a 1-indexed integer array nums of length n.

An element nums[i] of nums is called special if i divides n, i.e. n % i == 0.

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

 

Example 1:

Input: nums = [1,2,3,4]
Output: 21
Explanation: There are exactly 3 special elements in nums: nums[1] since 1 divides 4, nums[2] since 2 divides 4, and nums[4] since 4 divides 4. 
Hence, the sum of the squares of all special elements of nums is nums[1] * nums[1] + nums[2] * nums[2] + nums[4] * nums[4] = 1 * 1 + 2 * 2 + 4 * 4 = 21.

Example 2:

Input: nums = [2,7,1,19,18,3]
Output: 63
Explanation: There are exactly 4 special elements in nums: nums[1] since 1 divides 6, nums[2] since 2 divides 6, nums[3] since 3 divides 6, and nums[6] since 6 divides 6. 
Hence, the sum of the squares of all special elements of nums is nums[1] * nums[1] + nums[2] * nums[2] + nums[3] * nums[3] + nums[6] * nums[6] = 2 * 2 + 7 * 7 + 1 * 1 + 3 * 3 = 63.

 

Constraints:

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

Approach Overview

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.

Approach 1: Approach 1: Iterating through divisors

This approach involves iterating through all possible indices from 1 to n (inclusive) and checking if the index `i` divides `n` perfectly. If it does, it implies that the element at index `i` is a special element. We then calculate its square and sum up these squares to get the result.

The C solution uses a loop from 1 to numsSize to check divisibility. If i divides numsSize, the element at i-1 (0-indexed) is accessed, squared, and added to sum.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n)
Space Complexity: O(1) because we use only a constant amount of extra space.

Try this approach in the editor →

Approach 2: Approach 2: Using List Comprehension (or Equivalent)

Instead of explicitly using a loop, we can employ list comprehension (or equivalent methods) to create a filtered and mapped list of special numbers, square these numbers, and take their sum. This method works well in languages that support quick operations on lists.

This Python solution makes use of a list comprehension to succinctly filter and map the array indices. Only special numbers' squares contribute to the summation.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(n)
Space Complexity: O(n) due to list comprehension generating intermediate list.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Iterating through divisors

Time Complexity: O(n)
Space Complexity: O(1) because we use only a constant amount of extra space.

Approach 2: Using List Comprehension (or Equivalent)

Time Complexity: O(n)
Space Complexity: O(n) due to list comprehension generating intermediate list.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Iterating Through DivisorsO(sqrt(n))O(1)Best optimized approach when you want to avoid scanning the entire array
Direct EnumerationO(n)O(1)Simplest implementation; good for readability or small arrays
List Comprehension (Python/JS)O(n)O(1)Concise functional-style solution in high-level languages

Video Solution

6889. Sum of Squares of Special Elements | Leetcode Weekly Contest 354 | Solution Code. • Optimization • 672 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Sum of Squares of Special Elements easy or hard?
Sum of Squares of Special Elements is classified as an Easy problem on LeetCode with a high acceptance rate. The main requirement is recognizing that only indices dividing the array length should be considered.
Sum of Squares of Special Elements Python/Java solution
In Python, the solution is often written using a list comprehension that sums nums[i-1]**2 for every index i where n % i == 0. In Java, a loop from 1 to n performs the same divisor check and accumulates the squared values. Both implementations run in O(n) time with constant extra space.
How to solve Sum of Squares of Special Elements in O(n)?
Iterate through indices from 1 to n and check if n % i == 0. When the condition is true, square nums[i-1] and add it to a running sum. This linear scan processes each index once, resulting in O(n) time complexity and constant extra space.
Is Sum of Squares of Special Elements asked at Google/Amazon/Meta?
The problem itself appears on LeetCode as an Easy-level array and enumeration exercise. While this exact question may not frequently appear in interviews, the concept of divisor checks and index-based array conditions is common in coding interviews at companies like Google, Amazon, and Meta.
What is the best approach for Sum of Squares of Special Elements ?
The most efficient approach enumerates the divisors of the array length n. Only indices i where n % i == 0 can contribute to the sum, so checking divisors directly reduces work. This method runs in O(sqrt(n)) time and O(1) space while still accessing the needed elements in the array.
What data structure is used in Sum of Squares of Special Elements ?
The problem primarily uses a basic array. The logic focuses on index arithmetic and divisor checks rather than advanced data structures. Enumeration over array indices combined with simple math operations is sufficient.
What is the time complexity of Sum of Squares of Special Elements ?
A simple enumeration solution runs in O(n) time because it checks every index from 1 to n. An optimized solution enumerates only the divisors of n, reducing the time complexity to O(sqrt(n)). Both approaches use O(1) additional space.

Ready to solve this problem?

Practice Sum of Squares of Special Elements with our built-in code editor and test cases.

Practice on FleetCode
Previous

Sum of All Odd Length Subarrays

Next

Sum of Square Numbers