Sum of Squares of Special Elements

Easy

#2491Time: O(n), where `n` is the length of the `nums` array. We iterate through all `n` possible indices to check for divisibility.Space: O(1), as we only use a constant amount of extra space for variables like `sum` and the loop counter `i`.

Patterns

Enumeration

Data structures

Array

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly translates the problem statement into code. We iterate through all possible indices from 1 to n and check if each index i is a divisor of n. If it is, we add the square of the corresponding element to a running sum.

Algorithm

Initialize a variable sum to 0.
Get the length of the array, n.
Loop with an index i from 1 to n.
Inside the loop, check the condition n % i == 0.
If the condition is true, it means i is a divisor of n, and the element nums[i-1] (using 0-based indexing) is a "special" element.
Calculate the square of this special element, nums[i-1] * nums[i-1], and add it to sum.
After the loop completes, sum will hold the total sum of squares of all special elements. Return sum.

Walkthrough

The algorithm is straightforward:

Initialize a variable sum to 0.
Get the length of the array, n.
Loop with an index i from 1 to n.
Inside the loop, check the condition n % i == 0.
If the condition is true, it means i is a divisor of n, and the element nums[i-1] (using 0-based indexing) is a "special" element.
Calculate the square of this special element, nums[i-1] * nums[i-1], and add it to sum.
After the loop completes, sum will hold the total sum of squares of all special elements. Return sum.

1class Solution {2    public int sumOfSquares(int[] nums) {3        int n = nums.length;4        int sum = 0;5        for (int i = 1; i <= n; i++) {6            if (n % i == 0) {7                // The problem uses 1-based indexing for 'i',8                // so we access the array at index i-1.9                sum += nums[i - 1] * nums[i - 1];10            }11        }12        return sum;13    }14}

Complexity

Time

O(n), where `n` is the length of the `nums` array. We iterate through all `n` possible indices to check for divisibility.

Space

O(1), as we only use a constant amount of extra space for variables like `sum` and the loop counter `i`.

Trade-offs

Pros

Very simple and easy to understand and implement.
Directly follows the problem definition.

Cons

Slightly less efficient than an approach that optimizes finding divisors, although for the given constraints (n <= 50), the difference is negligible.

This approach improves upon the simple iteration by leveraging a property of divisors. If i is a divisor of n, then n/i is also a divisor. We can find all divisors by iterating only up to the square root of n. This reduces the number of iterations required.

Algorithm

Initialize a variable sum to 0.
Get the length of the array, n.
Loop with an index i from 1 up to floor(sqrt(n)).
Inside the loop, check if i is a divisor of n using the condition n % i == 0.
If i is a divisor:
- Add the square of the element at the 1-based index i (i.e., nums[i-1]) to sum.
- Find the corresponding divisor j = n / i.
- If i is not equal to j (this handles the case where n is a perfect square, to avoid double-counting the square root), add the square of the element at the 1-based index j (i.e., nums[j-1]) to sum.
After the loop, return sum.

Walkthrough

The core idea is to find pairs of divisors efficiently.

Initialize a variable sum to 0.
Get the length of the array, n.
Loop with an index i from 1 up to floor(sqrt(n)).
Inside the loop, check if i is a divisor of n using the condition n % i == 0.
If i is a divisor:
- Add the square of the element at the 1-based index i (i.e., nums[i-1]) to sum.
- Find the corresponding divisor j = n / i.
- If i is not equal to j (this handles the case where n is a perfect square, to avoid double-counting the square root), add the square of the element at the 1-based index j (i.e., nums[j-1]) to sum.
After the loop, return sum.

1class Solution {2    public int sumOfSquares(int[] nums) {3        int n = nums.length;4        int sum = 0;5        for (int i = 1; i * i <= n; i++) {6            if (n % i == 0) {7                // 'i' is a divisor8                sum += nums[i - 1] * nums[i - 1];9                10                int j = n / i;11                // 'j' is the corresponding divisor.12                // If i*i != n, then i and j are distinct divisors.13                if (i * i != n) {14                    sum += nums[j - 1] * nums[j - 1];15                }16            }17        }18        return sum;19    }20}

Complexity

Time

O(sqrt(n)), where `n` is the length of the `nums` array. The loop runs up to the square root of `n`, making it more efficient for larger `n`.

Space

O(1), as we only use a constant amount of extra space for variables like `sum`, `i`, and `j`.

Trade-offs

Pros

More time-efficient than the simple O(n) iteration, especially for larger n.
Reduces the number of checks needed to find all divisors.

Cons

The logic is slightly more complex due to handling pairs of divisors and the special case for perfect squares.
For the given small constraints (n <= 50), the performance gain is minimal and might not be noticeable.

Solutions

Solution

1class Solution { public int sumOfSquares ( int [] nums ) { int n = nums . length ; int ans = 0 ; for ( int i = 1 ; i <= n ; ++ i ) { if ( n % i == 0 ) { ans += nums [ i - 1 ] * nums [ i - 1 ]; } } return ans ; } }

1class Solution { public: int sumOfSquares ( vector < int >& nums ) { int n = nums . size (); int ans = 0 ; for ( int i = 1 ; i <= n ; ++ i ) { if ( n % i == 0 ) { ans += nums [ i - 1 ] * nums [ i - 1 ]; } } return ans ; } };

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem