### 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.