1. Problem Statement

You have n coins, and you want to arrange them in the shape of a staircase.
Each row k in the staircase contains exactly k coins.

Return the number of complete rows that can be formed.

Example 1:
Input: n = 5
Output: 2
Explanation:

• Row 1 has 1 coin
• Row 2 has 2 coins
• Row 3 would need 3 coins but only 2 remain → incomplete
  Thus, there are 2 complete rows.

Example 2:
Input: n = 8
Output: 3
Explanation:

• Row 1 → 1
• Row 2 → 2
• Row 3 → 3
• Total used = 6, remaining 2
  Row 4 incomplete → 3 full rows.

---

2. Key Insight

The total number of coins needed for k complete rows is given by the sum of the first k natural numbers: S=1+2+3+⋯+k=k(k+1)2S = 1 + 2 + 3 + \dots + k = \frac{k(k + 1)}{2}S=1+2+3+⋯+k=2k(k+1)​

We need to find the largest k such that: k(k+1)2≤n\frac{k(k + 1)}{2} \leq n2k(k+1)​≤n

This can be solved using:

1. Iterative subtraction (simple approach)
2. Binary search (efficient approach)
3. Mathematical formula using quadratic equation (constant-time approach)

---

3. Approach 1: Iterative Subtraction

Idea: Keep subtracting 1, 2, 3, ... from n until you don’t have enough coins.

Code:

public class ArrangingCoins {
    public int arrangeCoins(int n) {
        int row = 0;
        while (n >= row + 1) {
            row++;
            n -= row;
        }
        return row;
    }

    public static void main(String[] args) {
        ArrangingCoins obj = new ArrangingCoins();
        System.out.println(obj.arrangeCoins(5));  // Output: 2
        System.out.println(obj.arrangeCoins(8));  // Output: 3
        System.out.println(obj.arrangeCoins(1));  // Output: 1
    }
}

Complexity:

• Time: O(√n) (since sum of k numbers ~ k²/2 ≤ n ⇒ k ≈ √2n)
• Space: O(1)

Explanation:
We incrementally build each row until we cannot complete the next one.

---

4. Approach 2: Binary Search

We can find the largest k satisfying k(k + 1)/2 ≤ n.

Steps:

1. Set left = 0, right = n.
2. Check mid-point k = (left + right) / 2.
3. If k(k + 1)/2 ≤ n, move left to k + 1.
   Else move right to k - 1.
4. The result will be right (the largest valid k).

Code:

public class ArrangingCoins {
    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 (int) mid;
            if (coins < n) left = mid + 1;
            else right = mid - 1;
        }
        return (int) right;
    }

    public static void main(String[] args) {
        ArrangingCoins obj = new ArrangingCoins();
        System.out.println(obj.arrangeCoins(5));  // 2
        System.out.println(obj.arrangeCoins(8));  // 3
        System.out.println(obj.arrangeCoins(1804289383));  // large input
    }
}

Complexity:

• Time: O(log n)
• Space: O(1)

Reasoning: Binary search efficiently narrows down the largest possible k.

---

5. Approach 3: Mathematical Formula

From the inequality: k(k+1)/2≤nk(k + 1)/2 ≤ nk(k+1)/2≤n

Solving for k gives: k=−1+1+8n2k = \frac{-1 + \sqrt{1 + 8n}}{2}k=2−1+1+8n​​

We take the floor value because we only count complete rows.

Code:

public class ArrangingCoins {
    public int arrangeCoins(int n) {
        return (int)((Math.sqrt(1 + 8L * n) - 1) / 2);
    }

    public static void main(String[] args) {
        ArrangingCoins obj = new ArrangingCoins();
        System.out.println(obj.arrangeCoins(5));  // 2
        System.out.println(obj.arrangeCoins(8));  // 3
        System.out.println(obj.arrangeCoins(1));  // 1
    }
}

Complexity:

• Time: O(1)
• Space: O(1)

Explanation:
We derive k directly using the quadratic formula without loops.

---

6. Comparison of Approaches

Approach	Method	Time Complexity	Space Complexity	Notes
Iterative	Simple subtraction	O(√n)	O(1)	Easy to understand
Binary Search	Search by mid-value	O(log n)	O(1)	Efficient and precise
Mathematical	Direct formula	O(1)	O(1)	Fastest and elegant

---

7. Key Takeaways

• The problem is based on sum of first k natural numbers.
• The mathematical approach is the most optimal for interviews and large inputs.
• Always use long when computing k(k+1)/2 to avoid integer overflow.