Program to Find Sum of Series 1 + 2 + 2 + 3 + 3 + 3 + … + n in C++


The sum of series problems often serve as fundamental exercises in programming, helping developers grasp essential concepts such as loops, conditional statements, and arithmetic operations. In this article, we delve into the problem of finding the sum of the series 1 + 2 + 2 + 3 + 3 + 3 + … + n using C++. We'll explore different algorithms and implementation methods to achieve this task efficiently.

Understanding the Series:

Before we dive into the programming solutions, let's understand the series we're dealing with. The series comprises consecutive numbers where each number appears a specific number of times equal to its value. For instance, in the series 1 + 2 + 2 + 3 + 3 + 3, the number 1 appears once, the number 2 appears twice, and the number 3 appears thrice.

Mathematical Formulation

The series can be mathematically expressed as:

\( S_n = \sum_{k=1}^{n} k \times k \)

Where ( \( S_n \) ) represents the sum of the series up to the nth term.

Algorithm:

To find the sum of the series, we can use the following algorithm:

  1. Initialize the sum variable to 0.
  2. Iterate from 1 to n.
  3. Within each iteration, multiply the current number by its occurrence in the series and add it to the sum.
  4. Continue until the loop reaches n.
  5. Output the sum.

Method 1: Naive Approach

The simplest approach to solve this problem is by using a nested loop. The outer loop iterates through each number from 1 to n, and the inner loop repeats the number of times equal to the current value of the outer loop counter.

#include <iostream>

int main() {
    int n = 10; // Example value for n
    int sum = 0;

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= i; ++j) {
            sum += i;
        }
    }

    std::cout << "Sum of the series is: " << sum << std::endl;

    return 0;
}

This method has a time complexity of O(n^2) because of the nested loop.

Method 2: Optimized Approach

We can optimize the solution by using a single loop instead of a nested loop. Instead of multiplying each number by its occurrence, we can calculate the sum directly using a formula.

#include <iostream>

int main() {
    int n = 10; // Example value for n
    int sum = 0;

    for (int i = 1; i <= n; ++i) {
        sum += i * (i + 1) / 2;
    }

    std::cout << "Sum of the series is: " << sum << std::endl;

    return 0;
}

This method has a time complexity of O(n), making it more efficient than the naive approach.

Method 3: Recursive Approach

We can also solve this problem recursively. In each recursive call, we add the current number multiplied by its occurrence to the sum and decrement n until it reaches 0.

Algorithm

  1. If n is 0, return 0.
  2. Otherwise, return ( n^2 ) plus the sum of the series up to ( n-1 ).
#include <iostream>

int sumSeries(int n) {
    if (n == 0) return 0;
    return sumSeries(n - 1) + n * (n + 1) / 2;
}

int main() {
    int n = 10; // Example value for n
    int sum = sumSeries(n);
    std::cout << "Sum of the series is: " << sum << std::endl;
    return 0;
}

Though elegant, this method might not be as efficient as the iterative solutions due to the overhead of function calls.

Method 4: Mathematical Formula

Upon closer examination, we can deduce a formula to calculate the sum directly without iteration.

Algorithm

  1. Use the formula ( \( S_n = \frac{n(n + 1)(2n + 1)}{6} \) ) to calculate the sum.
  2. Return the result.
#include <iostream>
using namespace std;

int formulaSum(int n) {
    return n * (n + 1) * (2 * n + 1) / 6;
}

int main() {
    int n;
    cout << "Enter the value of n: ";
    cin >> n;
    cout << "The sum of the series is: " << formulaSum(n) << endl;
    return 0;
}

Conclusion:

In this article, we explored different methods to find the sum of the series 1 + 2 + 2 + 3 + 3 + 3 + … + n in C++. We discussed a naive approach using nested loops, an optimized approach with a single loop, and a recursive approach. Each method has its advantages and trade-offs in terms of simplicity, efficiency, and elegance. Choosing the right method depends on the specific requirements of the problem and the constraints of the system.

       

Advertisements

ads