2778. Sum of Squares of Special Elements
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:
-
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.
-
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. Theenumerate(nums, 1)
call starts the counting with 1, which aligns with the 1-indexed array described in the problem. -
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 indexi
is a divisor ofn
. -
Conditional Filter: The
if n % i == 0
part right after thefor
loop in the list comprehension acts as a filter. It includes only those elements in the final list whose indices are divisors ofn
. -
Square of Elements: For each element in the list that passed the filter condition, the square is calculated using
x * x
, wherex
is the value of the element innums
. -
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 thenums
array, withi
capturing the index (starting at 1) andx
capturing the value at each index.if n % i == 0
is the condition that checks if the indexi
is a divisor ofn
.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 EvaluatorExample 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.
-
We first determine the divisors of
n
. The divisors of 6 are 1, 2, 3, and 6. -
We then find the elements at these indices in the
nums
array:nums[1]
is 3 (since nums is 1-indexed)nums[2]
is 1nums[3]
is 4nums[6]
is 9
-
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)
- The square of
-
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.
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
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Don’t Miss This!