Calculate the Sum of Squares of the First N Natural Numbers in C#

Problem Description

In this problem, we are given a number n, and we need to calculate the sum of the squares of the first N natural numbers. In this article, we are going to discuss different approaches to solving this problem using C#.

Example 1

• Input: N = 4
• Output: 30
  

Explanation:

The squares of the first 4 natural numbers are: 1, 4, 9, 16.
The sum of the numbers is: 1 + 4 + 9 + 16 = 30.

Example 2

• Input: N = 6
• Output: 91

Explanation:

The squares of the first 6 natural numbers are: 1, 4, 9, 16, 25, 36.
The sum of the numbers is: 1 + 4 + 9 + 16 + 25 + 36 = 91.

Below are different approaches to calculating the sum of squares.

Using an Iterative Approach

This is a straightforward approach where we iterate through the numbers from 1 to N and calculate their squares. The squares are then summed up to get the result.

Implementation Code

using System;

class Program {
  static int SumOfSquaresIterative(int N) {
    int sum = 0;
    for (int i = 1; i <= N; i++) {
      sum += i * i; // Add square of the number to sum
    }
    return sum;
  }

  static void Main() {
    int N = 4;
    int result = SumOfSquaresIterative(N);
    Console.WriteLine("The sum of squares of the first {0} natural numbers is: {1}", N, result);
  }
}

Output:

The sum of squares of the first 4 natural numbers is: 30

Time Complexity: O(N)
Space Complexity: O(1)

Using Mathematical Formula

This approach reduces time complexity to O(1) from O(N) by using a direct formula to calculate the sum of squares of the first N natural numbers.

In this approach, we find the sum of the square of the first N natural numbers can be calculated directly using the formula:

Sum = N ? (N + 1) ? (2N + 1) / 6

Implementation Code

using System;

class Program {
  static int SumOfSquaresFormula(int N) {
    return (N * (N + 1) * (2 * N + 1)) / 6; // Formula for sum of squares
  }

  static void Main() {
    int N = 6;
    int result = SumOfSquaresFormula(N);
    Console.WriteLine("The sum of squares of the first {0} natural numbers is: {1}", N, result);
  }
}

Output:

The sum of squares of the first 6 natural numbers is: 91

Time Complexity: O(1)
Space Complexity: O(1)

Using Recursive Approach

In this approach, we use recursion to calculate the sum of squares. The base case is when N = 0, and the recursive case adds the square of N to the sum of squares of the first N ? 1 numbers.

Implementation Code

using System;

class Program {
  static int SumOfSquaresRecursive(int N) {
    // Base case: if N is 0, sum is 0
    if (N == 0)
      return 0;

    // Recursive case: sum of squares of N + (N-1)
    return (N * N) + SumOfSquaresRecursive(N - 1);
  }

  static void Main() {
    int N = 5;
    int result = SumOfSquaresRecursive(N);
    Console.WriteLine("The sum of squares of the first {0} natural numbers is: {1}", N, result);
  }
}

Output:

The sum of squares of the first 5 natural numbers is: 55

Time Complexity: O(N)
Space Complexity: O(N)

Real-Life Applications

• Mathematics and Statistics:
  The Sum of squares is used in statistical calculations, such as finding the variance or standard deviation of a dataset.
• Physics Simulations:
  The Sum of squares is used in physics to calculate energy levels or work done by forces.
• Data Analysis:
  The sum of squares is used in regression analysis and other optimization problems.