CL16BB - Editorial

PROBLEM LINK:

Practice
Contest

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.