# Sum of Squares of Special Elements 
**Difficulty:** EASY
[External](https://leetcode.com/problems/sum-of-squares-of-special-elements)
Canonical: https://scaleengineer.com/dsa/problems/sum-of-squares-of-special-elements
**Patterns:** [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Data structures:** Array
---
## Problem
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
## Simple Iteration
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.
**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`.
**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.
### Explanation
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`.

```java
class Solution {
    public int sumOfSquares(int[] nums) {
        int n = nums.length;
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            if (n % i == 0) {
                // The problem uses 1-based indexing for 'i',
                // so we access the array at index i-1.
                sum += nums[i - 1] * nums[i - 1];
            }
        }
        return 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`.

## Optimized Iteration using Divisor Properties
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.
**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`.
**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.
### Explanation
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`.

```java
class Solution {
    public int sumOfSquares(int[] nums) {
        int n = nums.length;
        int sum = 0;
        for (int i = 1; i * i <= n; i++) {
            if (n % i == 0) {
                // 'i' is a divisor
                sum += nums[i - 1] * nums[i - 1];
                
                int j = n / i;
                // 'j' is the corresponding divisor.
                // If i*i != n, then i and j are distinct divisors.
                if (i * i != n) {
                    sum += nums[j - 1] * nums[j - 1];
                }
            }
        }
        return sum;
    }
}
```
### 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`.

# Solutions
### Java

```java
class 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 ; } }
```

### CPP

```cpp
class 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 ; } };
```

### Python

```python
class 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 )
```