# 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;
} Author
Mayukh Datta