Arranging Coins

How it works

We can solve this directly with algebra. We need the largest k where k * (k + 1) / 2 <= n. Rearranging: k^2 + k - 2n <= 0. Using the quadratic formula, k = (-1 + sqrt(1 + 8n)) / 2.

Simplifying gives us k = sqrt(2n + 0.25) - 0.5. We take the floor of this value to get the answer.

Steps

1. Compute sqrt(2 * n + 0.25) - 0.5.
2. Return the integer part.

Complexity

• Time complexity: O(1) or O(sqrt {n}) depending on the language.
• Space complexity: O(1)

Things to watch for

Integer Overflow When Computing mid * (mid + 1)

When using binary search, computing mid * (mid + 1) can overflow for large values of mid if using 32-bit integers. Always cast to a larger type before multiplication.

Off-by-One Error in the Result

The formula k * (k + 1) / 2 gives the total coins needed for k complete rows. A common mistake is returning the wrong value when the sum exactly equals n or when determining whether to include the current row.

from math import sqrt

class Solution:
    def arrangeCoins(self, n: int) -> int:
        return int(sqrt(2 * n + 0.25) - 0.5)

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