Arranging Coins

A more efficient approach is to use binary search. We know that the number of coins required for k complete rows is 1 + 2 + ... + k = k * (k + 1) / 2. This is a monotonically increasing function of k. We can use binary search to find the largest k for which this sum is less than or equal to n.

• 1. Initialize left = 1, right = n, and result = 0.
• 2. While left <= right:
• 3. Calculate mid = left + (right - left) / 2. Use long to prevent overflow.
• 4. Calculate the coins needed for mid rows: coinsNeeded = mid * (mid + 1) / 2.
• 5. If coinsNeeded <= n:
  • mid is a potential answer. Store it: result = mid.
  • Search for a larger k: left = mid + 1.
• 6. Else (coinsNeeded > n):
  • mid is too large. Search for a smaller k: right = mid - 1.
• 7. Return result.

The problem asks for the largest integer k such that the sum of coins S_k = k * (k + 1) / 2 does not exceed n. Since S_k increases as k increases, we can efficiently search for k in the range [1, n]. We set up a binary search with left and right pointers. For each mid value, we calculate the coins needed, mid * (mid + 1) / 2. If the coins needed are less than or equal to n, it means mid could be our answer, and we should try for a larger k. So, we record mid and move our search to the right half (left = mid + 1). If the coins needed are more than n, mid is too large, and we must search in the left half (right = mid - 1). It's crucial to use long for intermediate calculations to avoid integer overflow, as n can be large.

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