### PROBLEM LINK:

**Author:** Sunny Aggarwal

**Tester:** Sergey Kulik

**Editorialist:** Sunny Aggarwal

### DIFFICULTY:

Cakewalk

### PREREQUISITES:

Implementaion, Mathematics, Brute Force.

### PROBLEM STATEMENT:

You are given a number N that represents the number of coins you have and you have to print the maximum possible height H of triangle which can be made from these coins in such a way that i^{th} row of the triangle contains i coins.

### QUICK EXPLANATION:

Maximum possible height of the triangle is the maximum possible value of H such that \frac{H\times(H+1)}{2} \le N.

### EXPLANATION:

It should be noted that i^{th} row of triangle contains i coins. Therefore, a traingle with H height will contain 1 coin in 1^{st} row, 2 coins in 2^{nd} row, … , H coins in H^{th} row and total number of coins required to build a triangle of height H will be equal to

As we are asked to find the maximum possible height of the triangle, we have to find the maximum value of H such that \frac{H \times (H+1)}{2} \le N. Note that the value of N ~= 10^9 in worst case and therefore the maximum possible value of H will be order of \sqrt{N}.

We can use following simple procedure to solve this problem.

int sum(int h) { return (h * (h+1) / 2); } void solve() { int n; cin >> n; int h = 1; while(sum(h) <= n) { h ++; } cout << h - 1 << "\n"; }

### TIME COMPLEXITY:

O(\sqrt{N})

### BONUS:

Try solving same problem with 1 \le N \le 10^{15}.

### AUTHOR’S AND TESTER’S SOLUTION:

Author’s solution can be found here.

Tester’s solution can be found here.