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 _thesum of the squares of all special elements of _nums.

Examples

Example 1

1
2
3
4

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

1
2
3
4

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

Solution

Approach

We iterate over all indices from 1 to n (1-indexed). If n % i == 0, nums[i-1] is special. We sum the squares of all such elements.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

#include <vector>
using namespace std;
class Solution {
public:
    int sumOfSquares(vector<int>& nums) {
        int n = nums.size(), res = 0;
        for (int i = 1; i <= n; ++i) {
            if (n % i == 0) res += nums[i-1] * nums[i-1];
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9

class Solution {
    public int sumOfSquares(int[] nums) {
        int n = nums.length, res = 0;
        for (int i = 1; i <= n; ++i) {
            if (n % i == 0) res += nums[i-1] * nums[i-1];
        }
        return res;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    fun sumOfSquares(nums: IntArray): Int {
        val n = nums.size
        var res = 0
        for (i in 1..n) {
            if (n % i == 0) res += nums[i-1] * nums[i-1]
        }
        return res
    }
}
1
2
3
4

class Solution:
    def sumOfSquares(self, nums: list[int]) -> int:
        n = len(nums)
        return sum(nums[i-1] ** 2 for i in range(1, n+1) if n % i == 0)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

impl Solution {
    pub fn sum_of_squares(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut res = 0;
        for i in 1..=n {
            if n % i == 0 {
                res += nums[i-1] * nums[i-1];
            }
        }
        res
    }
}
1
2
3
4
5
6
7
8

function sumOfSquares(nums: number[]): number {
    const n = nums.length;
    let res = 0;
    for (let i = 1; i <= n; ++i) {
        if (n % i === 0) res += nums[i-1] * nums[i-1];
    }
    return res;
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)