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.