Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

441. Arranging Coins - Leetcode Solution

Code Implementation

class Solution:
    def arrangeCoins(self, n: int) -> int:
        left, right = 0, n
        while left <= right:
            mid = (left + right) // 2
            curr = mid * (mid + 1) // 2
            if curr == n:
                return mid
            if curr < n:
                left = mid + 1
            else:
                right = mid - 1
        return right
      
class Solution {
public:
    int arrangeCoins(int n) {
        long left = 0, right = n;
        while (left <= right) {
            long mid = left + (right - left) / 2;
            long curr = mid * (mid + 1) / 2;
            if (curr == n) return (int)mid;
            if (curr < n) left = mid + 1;
            else right = mid - 1;
        }
        return (int)right;
    }
};
      
class Solution {
    public int arrangeCoins(int n) {
        long left = 0, right = n;
        while (left <= right) {
            long mid = left + (right - left) / 2;
            long curr = mid * (mid + 1) / 2;
            if (curr == n) return (int)mid;
            if (curr < n) left = mid + 1;
            else right = mid - 1;
        }
        return (int)right;
    }
}
      
var arrangeCoins = function(n) {
    let left = 0, right = n;
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        let curr = mid * (mid + 1) / 2;
        if (curr === n) return mid;
        if (curr < n) left = mid + 1;
        else right = mid - 1;
    }
    return right;
};

Problem Description

You are given an integer n representing the number of coins. Your task is to arrange these coins in a staircase shape, where the first row has 1 coin, the second row has 2 coins, the third row has 3 coins, and so on. Each subsequent row has exactly one more coin than the previous row. The goal is to find the total number of complete rows of the staircase that can be formed with all n coins. A complete row is one that is fully filled with coins; if you run out of coins before filling a row, that row is not counted.

Constraints:
  • You must use each coin only once.
  • There is exactly one valid answer for each input.
  • Input: n (0 ≤ n ≤ 231 - 1)

Thought Process

At first glance, the problem seems simple: just keep subtracting increasing numbers from n (1, then 2, then 3, etc.) until you can't subtract anymore. For example, subtract 1 from n, then 2, then 3, and so on, counting how many times you can do this before n becomes less than the next number to subtract. However, for very large values of n, this approach could be slow because it requires many iterations. To optimize, we can recognize that the total coins needed to form k complete rows is the sum of the first k natural numbers: k * (k + 1) / 2. We need to find the largest k such that this sum is less than or equal to n. This insight allows us to use a more efficient search technique (like binary search) instead of brute-force iteration.

Solution Approach

To solve the problem efficiently, we use the following steps:
  1. Mathematical Formula:
    The sum of the first k rows is k * (k + 1) / 2. Our goal is to find the largest integer k such that k * (k + 1) / 2 ≤ n.
  2. Binary Search:
    Since the sum increases rapidly as k increases, we can use binary search to efficiently find the largest valid k:
    • Initialize two pointers: left = 0 and right = n.
    • While left ≤ right:
      • Calculate mid = (left + right) // 2.
      • Calculate curr = mid * (mid + 1) // 2.
      • If curr == n, return mid (exact fit).
      • If curr < n, move left to mid + 1 (try more rows).
      • If curr > n, move right to mid - 1 (too many coins, try fewer rows).
    • When the loop ends, right will be the largest k such that the total coins used is not more than n.
  3. Why Binary Search?
    Binary search is efficient (O(log n) time) and works well here because the relationship between k and the sum is monotonic (always increasing).

Example Walkthrough

Example Input: n = 8
  • First, try filling rows:
    • Row 1: needs 1 coin (remaining: 7)
    • Row 2: needs 2 coins (remaining: 5)
    • Row 3: needs 3 coins (remaining: 2)
    • Row 4: needs 4 coins, but only 2 left (can't fill row 4)
    So, the answer is 3 complete rows.
  • Binary Search Steps:
    • left = 0, right = 8
    • mid = 4, curr = 4 * 5 / 2 = 10 (too high, right = 3)
    • mid = 1, curr = 1 (too low, left = 2)
    • mid = 2, curr = 3 (too low, left = 3)
    • mid = 3, curr = 6 (still low, left = 4)
    • Now, left (4) > right (3), so we return right = 3
    The answer is 3.

Time and Space Complexity

  • Brute-force Approach:
    Iteratively subtracting row sizes from n is O(k), where k is the answer (number of rows). In the worst case, this could be up to O(\sqrt{n}) (since the sum of numbers up to k approaches n).
  • Optimized (Binary Search) Approach:
    Each iteration splits the search space in half, so the time complexity is O(log n).
    Space complexity for both approaches is O(1) since only a few variables are used.

Summary

This problem asks how many complete rows of a coin staircase can be formed with a given number of coins. By recognizing the mathematical formula for the sum of the first k numbers, we can use binary search to efficiently find the answer. This approach is much faster than brute-force and demonstrates the power of combining mathematical insight with algorithmic techniques.