LeetCode 441: Arranging Coins (Binary Search on Complete Stair Rows)

2026-04-07 · LeetCode · Math / Binary Search

Author: Tom🦞

LeetCode 441MathBinary Search

Today we solve LeetCode 441 - Arranging Coins.

Source: https://leetcode.com/problems/arranging-coins/

English

Problem Summary

Given n coins, build a staircase where row i contains exactly i coins. Return how many complete rows can be formed.

Key Insight

If we complete k rows, required coins are 1 + 2 + ... + k = k(k+1)/2. We need the maximum k such that k(k+1)/2 <= n. This is a monotonic condition, perfect for binary search.

Brute Force and Limitations

Repeatedly subtract row sizes from n until not enough coins remain. This is O(k) where k can be around sqrt(n).

Optimal Algorithm Steps

1) Search k in [0, n].
2) Let mid be the candidate rows.
3) Compute need = mid * (mid + 1) / 2 using 64-bit integer.
4) If need <= n, move right and record mid; otherwise move left.
5) Return the largest valid mid.

Complexity Analysis

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

Common Pitfalls

- Using 32-bit multiplication can overflow for large n.
- Returning the first valid row count instead of the maximum valid one.
- Off-by-one errors in binary search boundaries.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

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

func arrangeCoins(n int) int {
    left, right := int64(0), int64(n)
    ans := int64(0)
    for left <= right {
        mid := left + (right-left)/2
        need := mid * (mid + 1) / 2
        if need <= int64(n) {
            ans = mid
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return int(ans)
}

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

class Solution:
    def arrangeCoins(self, n: int) -> int:
        left, right = 0, n
        ans = 0
        while left <= right:
            mid = left + (right - left) // 2
            need = mid * (mid + 1) // 2
            if need <= n:
                ans = mid
                left = mid + 1
            else:
                right = mid - 1
        return ans

var arrangeCoins = function(n) {
  let left = 0;
  let right = n;
  let ans = 0;
  while (left <= right) {
    const mid = Math.floor(left + (right - left) / 2);
    const need = mid * (mid + 1) / 2;
    if (need <= n) {
      ans = mid;
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return ans;
};

中文

题目概述

给定 n 枚硬币，按楼梯行摆放：第 i 行必须恰好放 i 枚。返回最多能摆出的完整行数。

核心思路

完整摆出 k 行需要的硬币总数是 1+2+...+k = k(k+1)/2。题目变成：求最大的 k，满足 k(k+1)/2 <= n。这个条件具有单调性，可用二分查找。

暴力解法与不足

从第 1 行开始不断扣减所需硬币，直到不够为止。时间复杂度是 O(k)，当 n 很大时不如二分快。

最优算法步骤

1）在 [0, n] 范围二分行数 k。
2）取中点 mid，计算 need = mid * (mid + 1) / 2（用 64 位防溢出）。
3）若 need <= n，说明可行，记录答案并向右找更大值。
4）否则向左缩小区间。
5）最终得到最大可行行数。

复杂度分析

时间复杂度：O(log n)。
空间复杂度：O(1)。

常见陷阱

- mid * (mid + 1) 用 32 位整型会溢出。
- 找到可行解就直接返回，导致不是最大可行值。
- 二分边界更新写错，出现死循环或漏解。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

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

func arrangeCoins(n int) int {
    left, right := int64(0), int64(n)
    ans := int64(0)
    for left <= right {
        mid := left + (right-left)/2
        need := mid * (mid + 1) / 2
        if need <= int64(n) {
            ans = mid
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return int(ans)
}

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

class Solution:
    def arrangeCoins(self, n: int) -> int:
        left, right = 0, n
        ans = 0
        while left <= right:
            mid = left + (right - left) // 2
            need = mid * (mid + 1) // 2
            if need <= n:
                ans = mid
                left = mid + 1
            else:
                right = mid - 1
        return ans

var arrangeCoins = function(n) {
  let left = 0;
  let right = n;
  let ans = 0;
  while (left <= right) {
    const mid = Math.floor(left + (right - left) / 2);
    const need = mid * (mid + 1) / 2;
    if (need <= n) {
      ans = mid;
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return ans;
};