Problem Statement

You have `n` coins to build a staircase where the i-th row has i coins. The goal is to find the number of complete rows in the staircase.

Approach 1: Brute Force (Iterative)

class Solution {
public:
    int arrangeCoins(int n) {
        int rows = 0;
        while (n >= rows + 1) {
            rows++;
            n -= rows;
        }
        return rows;
    }
};

 How it works:
1. We start building rows from 1 coin, 2 coins, 3 coins, and so on.
2. We keep track of remaining coins (n) and completed rows.
3. We stop when we can't complete the next row.

### Analysis:
- Time Complexity: O(√n) - We iterate until we run out of coins, which happens after approximately √(2n) rows.
- Space Complexity: O(1) - We only use a few variables.
- Pros: Simple to understand and implement.
- Cons: Not as efficient as the optimal solution for very large n.

## Approach 2: Binary Search

class Solution {
public:
    int arrangeCoins(int n) {
        long left = 0, right = n;
        while (left <= right) {
            long mid = left + (right - left) / 2;
            long coins = mid * (mid + 1) / 2;
            if (coins == n) return mid;
            if (coins < n) left = mid + 1;
            else right = mid - 1;
        }
        return right;
    }
};

### How it works:
1. We use binary search to find the maximum k where k(k+1)/2 <= n.
2. The formula k(k+1)/2 calculates the total coins needed for k complete rows.

### Analysis:
- Time Complexity: O(log n) - Binary search reduces the search space by half in each iteration.
- Space Complexity: O(1) - We only use a few variables.
- Pros: More efficient than the brute force approach, especially for large n.
- Cons: Slightly more complex to implement and understand.

## Approach 3: Mathematical Solution (Optimal)

class Solution {
public:
    int arrangeCoins(int n) {
        return (int)(sqrt(2LL * n + 0.25) - 0.5);
    }
};

### How it works:
1. We solve the quadratic equation: k(k+1)/2 = n
2. This gives us: k = √(2n + 1/4) - 1/2

### Analysis:
- Time Complexity: O(1) - Constant time operation.
- Space Complexity: O(1) - We only use a few variables.
- Pros: Most efficient solution, works in constant time regardless of n.
- Cons: Requires understanding of the mathematical derivation.

Addressing the Runtime Error:

The error occurs due to integer overflow when calculating 2*n for large values of n. To fix this, we need to use long long for the calculation:

class Solution {
public:
    int arrangeCoins(int n) {
        return (int)(sqrt(2LL * n + 0.25) - 0.5);
    }
};

The `2LL` ensures that the calculation is done using 64-bit integers, preventing overflow for large n.