Problem Link - Coins And Triangle in Binary Search

### Problem Statement:

Chef belongs to a very rich family which owns many gold mines. Today, he brought N gold coins and decided to form a triangle using these coins. Isn’t it strange? Chef has a unusual way of forming a triangle using gold coins, which is described as follows:

He puts **1** coin in the **1st** row, then puts **2** coins in the **2nd** row, then puts **3** coins in the **3rd** row, and so on.

Chef is interested in forming a triangle with maximum possible height using at most **N** coins. Can you tell him the maximum possible height of the triangle?

### Approach:

To form a triangle of height h, the total number of coins required is the sum of the first h natural numbers:

Total coins for height h=1+2+3+⋯+h=h(h+1)/2

**Using Binary Search:**- Initialize two pointers one with 1 and other with number of coins.
- Calculate the midpoint. Compute the total number of coins required for a triangle of height
`mid`

using the formula mid(mid+1)/2. - Check if the total number of coins for height
`mid`

is less than or equal to N - Update the answer to
`mid`

(as it is a valid height). - Move the
`lower_bound`

to`mid+1`

to check if a larger height is possible. - If the total number of coins for height
`mid`

exceeds N, reduce the`upper bound`

to`mid−1`

to try for a smaller height.

### Complexity:

**Time Complexity:**`O(log N)`

for binary search**Space Complexity:**`O(1)`

No extra space used.