# PROBLEM LINK:

*Author:* Sanchit Raina

*Tester:* Prajwal Sonwane

*Editorialist:* Sanchit Raina

# DIFFICULTY:

SIMPLE

# PREREQUISITES:

Math

# PROBLEM:

A shopkeeper in Starling City, sells ARROWS. He has decided to sell them for ₹1 for the first day,₹2 for next 2 days, ₹3 for next 3 days … ₹N for next N days. He sells only 1 arrow on a single day.

OLIVER, being the VIGILANTE buys all the available ARROWS on any day. Diggle is wondering the amount OLIVER needs to pay to the Shopkeeper after N days.

Since Diggle is busy right now. Can you find this amount for him?

# QUICK EXPLANATION:

To find sum of the series 1 + 2 + 2 + 3 + 3 + 3 … upto N terms

# EXPLANATION:

Here, we are required to find the sum of series, S(N) = 1 + 2 + 2 + 3 + 3 + 3 + 4 + 4 + 4 + 4 ... upto N terms.

The solution is easy(for smaller N), a simple loop to add all the numbers in the series, :

```
int sum=0,k=1,times=0;
for(int i=1;i<=n;i++){
sum=sum+k,times++;
if(times==k)times=0,k++;
}
```

But, for N \leq 1e9, this solution is surely going to lead to TLE. So, we need to think of improvising the solution.

## Hint

Think of breaking down the series into some known sums, which can be calculated in O(1). Think before you see the full solution.

## Full Solution

Ideally, this can be written as S(N) = S(K) + (K+1) + (K+1) + (K+1) …

, where S(K) = (1 * 1) + (2 * 2) + (3 * 3) + … + (K * K) = \sum_{n=1}^{n=K} n^{2},

and (K+1) is added N-x times, where x is the greatest integer less than N, such that it can be \sum_{n=1}^{n=K} n^{2}, i.e. sum of first K terms of the form a^{2}

# SOLUTIONS:

## Setter's Solution

```
#include <bits/stdc++.h>
#define ll long long
#define TEST ll T;cin>>T;while(T--)
using namespace std;
int main() {
TEST {
ll n;
cin >> n;
ll start = 0, i = 1;
while (start + i <= n) {
start += i;
i++;
}
ll k = i-1;
ll sum_of_k_sqaure_upto_i_minus_1 = (k*(k+1)*(2*k+1))/6;
ll ans = sum_of_k_sqaure_upto_i_minus_1;
ans += (n - start) * i;
cout << ans << '\n';
}
return 0;
}
```

Link to AC Solution : (Solution: 42194230 | CodeChef)