441. Arranging Coins - Explanation

Problem Link

Description

You have n coins and you want to build a staircase with these coins. The staircase consists of k rows where the ith row has exactly i coins. The last row of the staircase may be incomplete.

Return the number of complete rows of the staircase you will build.

Example 1:

#
# #
#

Input: n = 4

Output: 2

Example 2:

#
# #
# # #
# # #

Input: n = 9

Output: 3

Constraints:
1 <= n <= ((2^31) - 1)

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

Intuition

We are building a staircase where row 1 needs 1 coin, row 2 needs 2 coins, and so on. The question is: how many complete rows can we build with n coins?

The simplest approach is to simulate the process. Keep adding rows one by one, subtracting the required coins from n until we cannot complete another row.

Algorithm

1. Initialize row = 0.
2. While we have enough coins for the next row (n > row):
   • Increment row.
   • Subtract row coins from n.
3. Return row as the number of complete rows.

class Solution:
    def arrangeCoins(self, n: int) -> int:
        row = 0
        while n - row > 0:
            row += 1
            n -= row
        return row

Time & Space Complexity

• Time complexity: $O(\sqrt {n})$
• Space complexity: $O(1)$

---

2. Binary Search

Intuition

Building rows one by one is slow for large n. Instead, we can use the formula for the sum of first k integers: k * (k + 1) / 2. If this sum is at most n, we can build k complete rows.

This creates a monotonic condition perfect for binary search. We search for the largest k such that k * (k + 1) / 2 <= n.

Algorithm

1. Set search bounds: l = 1 and r = n.
2. While l <= r:
   • Compute mid and calculate coins needed for mid rows.
   • If coins needed exceeds n, search the left half.
   • Otherwise, update the result and search the right half.
3. Return the maximum valid k.

class Solution:
    def arrangeCoins(self, n: int) -> int:
        l, r = 1, n
        res = 0

        while l <= r:
            mid = (l + r) // 2
            coins = (mid * (mid + 1)) // 2
            if coins > n:
                r = mid - 1
            else:
                l = mid + 1
                res = max(res, mid)

        return res

Time & Space Complexity

• Time complexity: $O(\log n)$
• Space complexity: $O(1)$

---

3. Binary Search (Optimal)

Intuition

We can optimize the binary search by tightening the upper bound. Since k * (k + 1) / 2 <= n, we know k is roughly sqrt(2n). A safe upper bound is n / 2 + 1 for n > 3, which reduces the search space.

We also simplify the binary search by finding the first k where the condition fails, then returning k - 1.

Algorithm

1. Handle small cases: if n <= 3, return 1 for n = 1 and n - 1 otherwise.
2. Set l = 1 and r = n / 2 + 1.
3. Use binary search to find the smallest k where coins exceed n.
4. Return l - 1.

class Solution:
    def arrangeCoins(self, n: int) -> int:
        if n <= 3:
            return n if n == 1 else n - 1

        l, r = 1, (n // 2) + 1
        while l < r:
            mid = (l + r) // 2
            if (mid * (mid + 1)) // 2 <= n:
                l = mid + 1
            else:
                r = mid

        return l - 1

Time & Space Complexity

• Time complexity: $O(\log n)$
• Space complexity: $O(1)$

---

4. Bit Manipulation

Intuition

We can build the answer bit by bit, from the most significant bit down. For each bit position, we tentatively set it and check if the resulting number of rows is valid. If valid, we keep the bit; otherwise, we clear it.

Since n fits in 32 bits and k is roughly sqrt(n), we only need about 16 bits to represent the answer.

Algorithm

1. Start with a mask at the highest relevant bit (bit 15).
2. For each bit from high to low:
   • Set the bit in rows.
   • Calculate coins needed for rows rows.
   • If it exceeds n, clear the bit.
   • Shift mask right.
3. Return rows.

class Solution:
    def arrangeCoins(self, n: int) -> int:
        mask = 1 << 15
        rows = 0
        while mask > 0:
            rows |= mask
            coins = rows * (rows + 1) // 2
            if coins > n:
                rows ^= mask
            mask >>= 1
        return rows

Time & Space Complexity

• Time complexity: $O(1)$ since we iterate $15$ times.
• Space complexity: $O(1)$

---

5. Math

Intuition

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.

Algorithm

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

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

Time & Space Complexity

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

---

Common Pitfalls

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.

// Wrong: overflow when mid is large
int coins = mid * (mid + 1) / 2;

// Correct: cast to long first
long coins = (long) mid * (mid + 1) / 2;

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.

# Wrong: returning l instead of l - 1 after binary search
while l < r:
    mid = (l + r) // 2
    if mid * (mid + 1) // 2 <= n:
        l = mid + 1
    else:
        r = mid
return l  # Should be l - 1