Skip to main content
  1. Problem Solving Solutions/

O(1) solution for: 1+(1+2)+(1+2+3)+...+(1+2+3+...+n)

·1 min
Mayukh Datta
Problem Solving

The problem is to solve this series: 1+(1+2)+(1+2+3)+…+(1+2+3+…+n)

We can solve this in \(O(n)\) time if we apply the closed formula for the sum of \(N\) numbers. We need to traverse up till \(N\) and for each iteration calculate the sum of \(N\) numbers. But do you know what’s even better? You can solve it in \(O(1)\) time. To achieve that we have to dig deeper into the closed sum formula.

Let the \(N^{th} term\) of the series be \(S_{N}\), \[S_{N} = \sum_{i=1}^{N} i = \dfrac{N(N+1)}{2} = \dfrac{N^2+N}{2}\\ \sum_{i=1}^{N} S_{N} = \sum_{i=1}^{N} \dfrac{N^2+N}{2}\\ = \dfrac{1}{2} \sum_{i=1}^{N} N^2 + \sum_{i=1}^{N} N\\ = \dfrac{1}{2} \dfrac{N(N+1)(2N+1)}{6} + \dfrac{1}{2} \dfrac{N(N+1)}{2}\\ = \dfrac{1}{2}N(N+1) [\dfrac{2N+1}{6} + \dfrac{1}{2}]\\ = \dfrac{N(N+1)(2N+4)}{12}\] \[\therefore S_{N} = \dfrac{N(N+1)(2N+4)}{12}\]

C++ Solution:

#include<bits/stdc++.h>
using namespace std;
int main(void)
{
	int t;
	long n, sum = 0;
	cin >> t;
	while(t--){
	    cin >> n;
	    sum = ((n \* (n + 1)) \* ((2 \* n) + 4)) / 12;
	    cout << sum << endl;
	}
	return 0;
}