2778. Sum of Squares of Special Elements

EasyArraySimulation
Leetcode Link

Problem Description

In this problem, we are presented with an array of integers nums which uses 1-indexing, meaning the first element is considered at position 1, the second at position 2, and so on. The array's length is denoted as n. A special element within this array is defined as an element nums[i] where the index i is a divisor of n (the array's length), i.e., n % i == 0.

Our task is to find the sum of the squares of all the special elements in the nums array. This sum is the outcome we are required to return.

Intuition

The solution hinges on the simple observation that we only need to consider elements at indices which are divisors of the array length n. To find these indices, we iterate over the array, starting at the 1st element (index 1), and continue to the last element (index n). For each element nums[i], we check if i is a divisor of n by using the modulus operation n % i. If the result of this operation is 0, it means that i is a divisor of n, and we consider nums[i] a special element.

Once we identify a special element, we take its square and add it to an accumulator that is tracking the sum of squares. The concise Python code uses list comprehension, which is a compact way to process lists and apply operations to each element. By iterating over nums with enumerate, we get both the element and its 1-based index in each iteration. We filter for the indices that are divisors of n and calculate the square of their corresponding values, summing them all up in one line.

The elegance of the solution comes from its efficiency—there is no need to check every index against every other number to find divisors and only a single pass through the array is required. This makes the solution very efficient in terms of time complexity, having an O(n) runtime where n is the number of elements in the nums array.

Solution Approach

The implementation of the given solution approach uses a few key Python concepts: list comprehension, the enumerate function, and the modulus operator. Since no specific algorithms or complex data structures are involved in this solution, it is straightforward and elegant due to its direct logic.

A breakdown of the steps in the solution implemented in the Python code is as follows:

  1. List Comprehension: A powerful feature in Python that allows us to create a list based on an existing list. It is often used to apply an operation to each element in the list.

  2. enumerate Function: This is a built-in Python function that adds a counter to an iterable. In this case, it is used to get both the element and its index from the nums array. The enumerate(nums, 1) call starts the counting with 1, which aligns with the 1-indexed array described in the problem.

  3. Modulus Operator (%): This operator is used to find the remainder of the division of two numbers. In our case, it is used to check if the index i is a divisor of n.

  4. Conditional Filter: The if n % i == 0 part right after the for loop in the list comprehension acts as a filter. It includes only those elements in the final list whose indices are divisors of n.

  5. Square of Elements: For each element in the list that passed the filter condition, the square is calculated using x * x, where x is the value of the element in nums.

  6. Sum Function: To combine all the squared values into a single sum, the built-in sum() function is used.

The combination of these elements results in the following single line of Python code, which constitutes the core of the solution:

return sum(x * x for i, x in enumerate(nums, 1) if n % i == 0)

Here's the explanation of how the code executes:

  • for i, x in enumerate(nums, 1) iterates through the nums array, with i capturing the index (starting at 1) and x capturing the value at each index.
  • if n % i == 0 is the condition that checks if the index i is a divisor of n.
  • x * x computes the square of the element if the condition is true.
  • sum() adds up all the squared values that meet the condition, resulting in the sum of the squares of all special elements.

In essence, the solution loops through the array once, checking the divisibility of each index and squaring and summing the values in one seamless operation, which makes it both efficient and clean.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's go through a small example to illustrate the solution approach described above.

Assume we are given the following array nums with 1-indexing where the array length n is 6:

nums = [3, 1, 4, 1, 5, 9]

Remember that a "special element" in this context means nums[i] where i is a divisor of n (which is 6 in this case).

We want to find the sum of the squares of all such special elements.

  1. We first determine the divisors of n. The divisors of 6 are 1, 2, 3, and 6.

  2. We then find the elements at these indices in the nums array:

    • nums[1] is 3 (since nums is 1-indexed)
    • nums[2] is 1
    • nums[3] is 4
    • nums[6] is 9
  3. Now, we calculate the square of each of these special elements:

    • The square of nums[1] (which is 3) is (3^2 = 9)
    • The square of nums[2] (which is 1) is (1^2 = 1)
    • The square of nums[3] (which is 4) is (4^2 = 16)
    • The square of nums[6] (which is 9) is (9^2 = 81)
  4. We add up these squared values to get the sum:

    (9 (from\ nums[1]) + 1 (from\ nums[2]) + 16 (from\ nums[3]) + 81 (from\ nums[6]) = 107)

Therefore, the result for the example problem, which is the sum of the squares of the special elements, is 107.

The Python code implementing this using the given solution approach would look like this:

nums = [3, 1, 4, 1, 5, 9]
n = len(nums)
result = sum(x * x for i, x in enumerate(nums, 1) if n % i == 0)

After executing this code, the variable result would hold the value 107, which is the correct answer to our example problem.

Solution Implementation

1class Solution:
2    def sumOfSquares(self, nums: List[int]) -> int:
3        # Calculate the length of the input list
4        length = len(nums)
5      
6        # Use a list comprehension to find the sum of squares of the elements
7        # that correspond to indices which are divisors of the list's length
8        sum_of_squares = sum(x * x for index, x in enumerate(nums, start=1) if length % index == 0)
9
10        # Return the calculated sum of squares
11        return sum_of_squares
12
13# The enumerate function in the list comprehension is used to iterate over
14# the nums list along with the indices, starting from 1. The condition inside
15# the list comprehension checks if the current index is a divisor of the 
16# length of the list by checking if the remainder of the division is 0.
17# If the condition is True, the square of the number at the current index (x * x)
18# is included in the sum_of_squares. The sum function then adds up all
19# the squared values to give the final result.
20
1class Solution {
2    // This method calculates the sum of squares of specific elements in the array.
3    // It adds the square of the number at the index that is a divisor of the length of the array.
4    public int sumOfSquares(int[] nums) {
5        // 'n' represents the length of the input array 'nums'.
6        int n = nums.length;
7        // 'sum' will hold the cumulative sum of squares of selected elements.
8        int sum = 0;
9      
10        // We iterate over all possible divisors of 'n', starting from 1 to 'n' inclusive.
11        for (int i = 1; i <= n; ++i) {
12            // We check if 'i' is a divisor of 'n'.
13            if (n % i == 0) {
14                // If 'i' is a divisor, add the square of the element at the (i - 1)th index to 'sum'.
15                // Since array indices in Java are 0-based, we access the element using 'i - 1'.
16                sum += nums[i - 1] * nums[i - 1];
17            }
18        }
19        // The method returns the calculated sum.
20        return sum;
21    }
22}
23
1#include <vector> // Include the header for std::vector
2
3class Solution {
4public:
5    // Function to calculate the sum of squares of elements at indices which are divisors of the vector's size.
6    int sumOfSquares(std::vector<int>& nums) {
7        int size = nums.size(); // Store the size of the vector
8        int totalSum = 0; // Initialize the sum accumulator
9      
10        // Loop over the elements of the vector starting at index 1 (not 0)
11        for (int index = 1; index <= size; ++index) {
12            // If the current index is a divisor of the vector's size
13            if (size % index == 0) {
14                // Add the square of the corresponding element to the total sum.
15                // Note that we subtract 1 from the index since C++ arrays are 0-based.
16                totalSum += nums[index - 1] * nums[index - 1];
17            }
18        }
19      
20        // Return the total sum of the squares.
21        return totalSum;
22    }
23};
24
1/**
2 * Calculates the sum of the squares of elements in the given array 
3 * `nums` where the element's index plus one is a divisor of the array's length.
4 * @param nums An array of numbers.
5 * @return The sum of the squares of selected elements.
6 */
7function sumOfSquares(nums: number[]): number {
8  // Get the number of elements in the array `nums`.
9  const arrayLength = nums.length;
10  // Initialize the variable to hold the sum of the squares.
11  let sum = 0;
12  // Iterate over the array `nums`.
13  for (let index = 0; index < arrayLength; ++index) {
14    // Check if index plus one is a divisor of the array's length.
15    if (arrayLength % (index + 1) === 0) {
16      // If so, add the square of the current element to the sum.
17      sum += nums[index] * nums[index];
18    }
19  }
20  // Return the computed sum of squares.
21  return sum;
22}
23

Time and Space Complexity

Time Complexity

The time complexity of the given code is O(n), where n is the length of the nums list. This is because the function iterates over all elements in the list exactly once. The condition n % i == 0 can be checked in constant time for each iteration, so it does not add to the complexity order.

Space Complexity

The space complexity of the code is O(1). No additional space is required that is dependent on the input list size, as the summation is done on-the-fly and only the sum variable (x * x for i, x in enumerate(nums, 1) if n % i == 0) is being maintained throughout the loop.

Learn more about how to find time and space complexity quickly using problem constraints.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Recommended Readings

Want a Structured Path to Master System Design Too? Don’t Miss This!