### PROBLEM LINK:

**Author:** Subham Das

**Tester:** Soumik Sarkar

**Editorialist:** Soumik Sarkar

### DIFFICULTY:

CAKEWALK

### PREREQUISITES:

Aritmethic progression

### PROBLEM:

Given the sum of the series **1, 2, 3, 4, 5…** (the last term may not satisfy the series), find the number of terms of the series.

### EXPLANATION:

The total value **N** is provided. Let the number of terms of the series be **K**. Then one can use the following algorithm to get the value of **K**

K = 1 sum = 0 while sum < N sum = sum + K K = K + 1

The complexity of this approach is \mathcal{O}(K).

There exists a better approach. We know that 1+2+3+....+K = K\times(K+1)/2. Thus, we can state

N = K \times (K+1)/2

\implies K^2 + K - 2N = 0

\implies K = \dfrac{-1 + \sqrt{1^2+4 \times 1 \times 2N}}{2} \quad (disregarding the negative solution)

\implies K = \dfrac{\sqrt{1+8N} - 1}{2}

Since the last value of the series may not be a part of the series, **N** too may not be a part of the sum series **1, 3, 6, 10…** Consequently, **K** determined with this formula may not be a whole number. The answer will then be \lceil K \rceil.

Complexity of the above approach is \mathcal{O}(1).

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.