Scale Engineer

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.
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;    }}

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.

Solutions

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 ; } }

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 →

Next problem