Given a non-negative integer **n**, compute and return the sum of

1^{2} + 2^{2} + 3^{2} + ... + n^{2}

The core challenge of this problem is to compute the sum of squares of the first `n`

natural numbers efficiently. This problem is significant in various mathematical and computational applications, such as statistical calculations and algorithm analysis. A common pitfall is to misunderstand the range of numbers to be squared or to overlook the efficiency of the solution.

To solve this problem, we can start with a naive approach and then discuss an optimized solution.

The naive solution involves iterating through each number from 1 to `n`

, squaring it, and adding it to a running total. This approach is straightforward but not the most efficient for very large values of `n`

.

An optimized solution leverages the mathematical formula for the sum of squares of the first `n`

natural numbers:

Sum = n(n + 1)(2n + 1) / 6

This formula allows us to compute the sum in constant time, O(1), which is significantly faster than the iterative approach.

- Initialize a variable
`sum`

to 0. - Iterate through numbers from 1 to
`n`

. - For each number
`i`

, compute`i * i`

and add it to`sum`

. - Return the value of
`sum`

.

- Use the formula
`Sum = n(n + 1)(2n + 1) / 6`

to compute the sum directly. - Return the computed value.

```
public class SumOfSquares {
public static int sumOfSquares(int n) {
int sum = 0; // Initialize sum to 0
for (int i = 1; i <= n; i++) { // Iterate from 1 to n
sum += i * i; // Add the square of i to sum
}
return sum; // Return the computed sum
}
public static void main(String[] args) {
int n = 3;
System.out.println(sumOfSquares(n)); // Output: 14
}
}
```

```
public class SumOfSquares {
public static int sumOfSquares(int n) {
// Use the formula to compute the sum of squares
return n * (n + 1) * (2 * n + 1) / 6;
}
public static void main(String[] args) {
int n = 3;
System.out.println(sumOfSquares(n)); // Output: 14
}
}
```

**Naive Approach:** The time complexity is O(n) because we iterate through each number from 1 to `n`

. The space complexity is O(1) as we use a constant amount of extra space.

**Optimized Approach:** The time complexity is O(1) because we compute the sum using a constant-time formula. The space complexity is also O(1).

Consider the following edge cases:

**n = 0:**The sum should be 0.**n = 1:**The sum should be 1.**Large values of n:**Ensure the solution handles large values without overflow.

To test the solution comprehensively, consider the following test cases:

n = 0; Expected output: 0 n = 1; Expected output: 1 n = 3; Expected output: 14 n = 10; Expected output: 385 n = 100; Expected output: 338350

When approaching such problems, consider both iterative and mathematical solutions. Understanding mathematical formulas can often lead to more efficient solutions. Practice by solving similar problems and studying different algorithms to improve problem-solving skills.

In this blog post, we discussed how to compute the sum of squares of the first `n`

natural numbers using both naive and optimized approaches. Understanding and applying mathematical formulas can significantly improve the efficiency of your solutions. Keep practicing and exploring further to enhance your problem-solving abilities.