Sum of Squares of Special Elements solution and explanation
Google
9 more videos on this problem
6889. Sum of Squares of Special Elements | Leetcode Weekly Contest 354 | Solution Code.Optimization · 0:12 · 672 views
Leetcode Weekly contest 354 - Easy - Sum of Squares of Special ElementsPrakhar Agrawal · 2:00 · 394 views
LeetCode 2778 : Sum of Squares of Special Elements || EASY || C++ || JAVA || Detailed SolutionCodeGPT · 4:25 · 346 views
Sum of Squares of Special Elements | Leetcode 2778 | Contest 354Tech Courses · 2:59 · 331 views
2778. Sum of Squares of Special Elements (Leetcode Easy)Programming Live with Larry · 2:05 · 251 views
2778 Sum of Squares of Special Elements | Leetcode Weekly Contest 354 | First Problem | EasyAman Babu · 1:57 · 193 views
LeetCode WEEKLY 354 java solution (6889. Sum of Squares of Special Elements)Ssquare · 0:37 · 165 views
2778. Sum of Squares of Special Elements || Leetcode || Weekly Contest 354 || HindiAshish Kumar · 0:48 · 130 views
Sum of Squares of Special Elements Leetcode - 2778 | Coder InfinityCoder Infinity · 1:27 · 103 views
2778. Sum of Squares of Special ElementsLetsCode · 1:45 · 76 views
The 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 <= 501 <= nums[i] <= 50
Approach overview
Problem Overview: Given an array nums of length n, an element is considered special if its 1-indexed position i divides n (i.e., n % i == 0). The task is to square each special element and return the total sum.
Approach 1: Iterating Through Divisors (O(sqrt(n)) time, O(1) space)
The key observation: instead of scanning every index, only positions that divide n can contribute to the result. Iterate through all divisors of n up to sqrt(n). For each divisor d, both d and n/d are valid positions in the array. Convert them to 0-based indices and add the square of the corresponding values. Handle the case where d == n/d to avoid double counting. This reduces unnecessary checks and focuses only on valid positions. The method uses constant extra memory and leverages basic math and divisor enumeration logic.
Approach 2: Using List Comprehension or Direct Enumeration (O(n) time, O(1) extra space)
A straightforward solution iterates through every index from 1 to n. For each position, check if n % i == 0. If true, square nums[i-1] and add it to the running total. In Python or JavaScript, this can be expressed compactly using list comprehension or functional iteration. While slightly less efficient than divisor enumeration for very large arrays, the code is extremely readable and performs well within typical constraints. This approach fits naturally with problems focused on array traversal and simple enumeration.
Recommended for interviews: Start with the direct enumeration approach because it clearly demonstrates you understand the condition n % i == 0. Then mention the divisor-based optimization. Enumerating divisors of n shows stronger algorithmic thinking and reduces the checks from O(n) to O(sqrt(n)), which is the most efficient approach.
Approach 1: Approach 1: Iterating through divisors
This approach involves iterating through all possible indices from 1 to n (inclusive) and checking if the index `i` divides `n` perfectly. If it does, it implies that the element at index `i` is a special element. We then calculate its square and sum up these squares to get the result.
def sum_of_squares(nums):
n = len(nums)
sum = 0
for i in range(1, n + 1):
if n % i == 0:
sum += nums[i - 1] ** 2
return sum
nums = [1, 2, 3, 4]
print(sum_of_squares(nums)) # Output: 21public class SumOfSquares {
public static int sumOfSquares(int[] nums) {
int sum = 0;
int n = nums.length;
for (int i = 1; i <= n; i++) {
if (n % i == 0) {
sum += nums[i-1] * nums[i-1];
}
}
return sum;
}
public static void main(String[] args) {
int[] nums = {1, 2, 3, 4};
System.out.println(sumOfSquares(nums)); // Output: 21
}
}#include <iostream>
#include <vector>
int sumOfSquares(const std::vector<int>& nums) {
int sum = 0;
int n = nums.size();
for (int i = 1; i <= n; ++i) {
if (n % i == 0) {
sum += nums[i-1] * nums[i-1];
}
}
return sum;
}
int main() {
std::vector<int> nums = {1, 2, 3, 4};
std::cout << sumOfSquares(nums) << std::endl; // Output: 21
return 0;
}function sumOfSquares(nums) {
const n = nums.length;
let sum = 0;
for (let i = 1; i <= n; i++) {
if (n % i === 0) {
sum += nums[i - 1] ** 2;
}
}
return sum;
}
const nums = [1, 2, 3, 4];
console.log(sumOfSquares(nums)); // Output: 21#include <stdio.h>
int sumOfSquares(int* nums, int numsSize) {
int sum = 0;
for (int i = 1; i <= numsSize; ++i) {
if (numsSize % i == 0) {
sum += nums[i-1] * nums[i-1];
}
}
return sum;
}
int main() {
int nums[] = {1, 2, 3, 4};
int n = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", sumOfSquares(nums, n)); // Output: 21
return 0;
}using System;
class Program {
static int SumOfSquares(int[] nums) {
int sum = 0;
int n = nums.Length;
for (int i = 1; i <= n; i++) {
if (n % i == 0) {
sum += nums[i - 1] * nums[i - 1];
}
}
return sum;
}
static void Main() {
int[] nums = {1, 2, 3, 4};
Console.WriteLine(SumOfSquares(nums)); // Output: 21
}
}Here, we iterate through the numbers from 1 to len(nums), checking divisibility to identify special indices. Each special index’s element is squared and added to sum.
Time Complexity: O(n)
Space Complexity: O(1), with only a single integer sum variable used.
Approach 2: Approach 2: Using List Comprehension (or Equivalent)
Instead of explicitly using a loop, we can employ list comprehension (or equivalent methods) to create a filtered and mapped list of special numbers, square these numbers, and take their sum. This method works well in languages that support quick operations on lists.
def sum_of_squares(nums):
n = len(nums)
return sum([nums[i - 1] ** 2 for i in range(1, n + 1) if n % i == 0])
nums = [1, 2, 3, 4]
print(sum_of_squares(nums)) # Output: 21function sumOfSquares(nums) {
const n = nums.length;
return Array.from({ length: n }, (_, i) => i + 1)
.filter(i => n % i === 0)
.reduce((sum, i) => sum + nums[i - 1] ** 2, 0);
}
const nums = [1, 2, 3, 4];
console.log(sumOfSquares(nums)); // Output: 21This Python solution makes use of a list comprehension to succinctly filter and map the array indices. Only special numbers' squares contribute to the summation.
Time Complexity: O(n)
Space Complexity: O(n) due to list comprehension generating intermediate list.
Approach 3: Default Approach
function sumOfSquares(nums: number[]): number {
const n = nums.length;
let ans = 0;
for (let i = 0; i < n; ++i) {
if (n % (i + 1) === 0) {
ans += nums[i] * nums[i];
}
}
return ans;
}func sumOfSquares(nums []int) (ans int) {
n := len(nums)
for i, x := range nums {
if n%(i+1) == 0 {
ans += x * x
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Iterating through divisors | Time Complexity: O(n) |
| Approach 2: Using List Comprehension (or Equivalent) | Time Complexity: O(n) |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterating Through Divisors | O(sqrt(n)) | O(1) | Best optimized approach when you want to avoid scanning the entire array |
| Direct Enumeration | O(n) | O(1) | Simplest implementation; good for readability or small arrays |
| List Comprehension (Python/JS) | O(n) | O(1) | Concise functional-style solution in high-level languages |
Frequently asked questions
Is Sum of Squares of Special Elements easy or hard?
Sum of Squares of Special Elements is classified as an Easy problem on LeetCode with a high acceptance rate. The main requirement is recognizing that only indices dividing the array length should be considered.
Sum of Squares of Special Elements Python/Java solution
In Python, the solution is often written using a list comprehension that sums nums[i-1]**2 for every index i where n % i == 0. In Java, a loop from 1 to n performs the same divisor check and accumulates the squared values. Both implementations run in O(n) time with constant extra space.
How to solve Sum of Squares of Special Elements in O(n)?
Iterate through indices from 1 to n and check if n % i == 0. When the condition is true, square nums[i-1] and add it to a running sum. This linear scan processes each index once, resulting in O(n) time complexity and constant extra space.
Is Sum of Squares of Special Elements asked at Google/Amazon/Meta?
The problem itself appears on LeetCode as an Easy-level array and enumeration exercise. While this exact question may not frequently appear in interviews, the concept of divisor checks and index-based array conditions is common in coding interviews at companies like Google, Amazon, and Meta.
What is the best approach for Sum of Squares of Special Elements ?
The most efficient approach enumerates the divisors of the array length n. Only indices i where n % i == 0 can contribute to the sum, so checking divisors directly reduces work. This method runs in O(sqrt(n)) time and O(1) space while still accessing the needed elements in the array.
What data structure is used in Sum of Squares of Special Elements ?
The problem primarily uses a basic array. The logic focuses on index arithmetic and divisor checks rather than advanced data structures. Enumeration over array indices combined with simple math operations is sufficient.
What is the time complexity of Sum of Squares of Special Elements ?
A simple enumeration solution runs in O(n) time because it checks every index from 1 to n. An optimized solution enumerates only the divisors of n, reducing the time complexity to O(sqrt(n)). Both approaches use O(1) additional space.