algoadvance

Leetcode 2778. Sum of Squares of Special Elements

Problem Statement

You’re given a 1-indexed integer array nums of length n.

An element nums[i] is special if i divides n, i.e., n % i == 0.

Return the sum of the squares of all special elements.

Clarifying Questions

1. Can the array contain negative numbers?
   • Yes, the array can contain negative numbers.
2. What is the range of n (length of nums)?
   • Assume 1 <= n <= 10^4.
3. Are we guaranteed that the array contains at least one element which is special?
   • Yes, since i = 1 always divides n, there’s at least one special element.

Strategy

1. Initialization: We need to iterate through each index i from 1 to n.
2. Check for Special Element: For each index i, check if i divides n without leaving a remainder (i.e., n % i == 0).
3. Sum of Squares: If the element is special, compute its square and add it to the running sum.
4. Edge Cases: Ensure that we handle the smallest (n = 1) and largest (n = 10^4) possible values of the array length efficiently.

Code

#include <iostream>
#include <vector>

int sumOfSquares(std::vector<int>& nums) {
    int n = nums.size();
    int sum = 0;
    
    for (int i = 1; i <= n; ++i) {
        if (n % i == 0) {
            sum += nums[i - 1] * nums[i - 1];  // Since the array is 1-indexed based on the problem
        }
    }
    
    return sum;
}

int main() {
    std::vector<int> nums = {1, 2, 3, 4, 5};  // Example input
    std::cout << sumOfSquares(nums) << std::endl;  // Expected output: 1 + 4 + 25 = 30
    return 0;
}

Time Complexity

• Time Complexity: (O(n))
  • We iterate through the array exactly once.
  • For each element, we perform a constant time operation to check if it’s special and potentially add to the sum.
• Space Complexity: (O(1))
  • We use a fixed amount of additional space regardless of the size of the input array.

This implementation ensures that it efficiently computes the sum of squares for special elements in linear time with respect to the size of the input array.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?