💬 Discord
Sign In
NeetCode #263LC-441EasyBinary Search
← Back to All Problems

#263 · #441 · Arranging Coins(排列硬币)

📌 Problem Statement & Constraints

You have n coins and want to build a staircase where the i-th row has exactly i coins. Return the number of complete rows. Constraints: 1 <= n <= 2^31 - 1.

💡 Core Algorithmic Approaches

  1. Find the largest k with k * (k + 1) / 2 <= n. That is a monotone predicate, so binary search applies.
  2. The range is [0, n], and the upper-biased midpoint finds the largest valid k.
  3. A closed form also exists: k = floor((sqrt(8n + 1) - 1) / 2), but it needs care with floating-point precision for large n.
  4. The binary search is exact and needs no precision handling.

💻 Benchmark Python3 Implementation

class Solution:
    def arrangeCoins(self, n: int) -> int:
        lo, hi = 0, n
        while lo < hi:
            mid = (lo + hi + 1) // 2   # upper-biased: find the largest valid k
            if mid * (mid + 1) // 2 <= n:
                lo = mid
            else:
                hi = mid - 1
        return lo


# Closed-form variant with an integer-sqrt correction
class Solution2:
    def arrangeCoins(self, n: int) -> int:
        from math import isqrt
        k = (isqrt(8 * n + 1) - 1) // 2
        # correct any off-by-one from the integer square root
        while (k + 1) * (k + 2) // 2 <= n:
            k += 1
        return k

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(log n) for binary search; O(1) for the closed form with a bounded correction.
💾 Space Complexity
O(1): a few scalars.

⚠️ Interview Pitfalls & Follow-ups

  • Using the lower-biased midpoint with lo = mid: infinite loop when hi == lo + 1.
  • Using math.sqrt directly: floating-point rounding can be off by one for n near 2^31; the correction loop or isqrt is safer.
  • Comparing mid * (mid + 1) <= 2 * n: equivalent and avoids the division, but the triangular formula is clearer.
  • Returning the number of coins rather than the rows: the answer is k, the number of complete rows.