LeetCode 441: Arranging Coins

Problem Restatement

We are given n coins.

We want to arrange them into a staircase shape.

The staircase must follow this rule:

Each row must contain exactly one more coin than the previous row.

We need to return the number of complete rows that can be formed.

The last row may be incomplete, and incomplete rows do not count.

The official problem asks for the number of complete staircase rows that can be formed using exactly n coins. (leetcode.com)

Input and Output

Example function shape:

def arrangeCoins(n: int) -> int:
    ...

Examples

Example 1:

n = 5

We build rows:

row 1 -> 1 coin
row 2 -> 2 coins
row 3 -> needs 3 coins

After the first two rows:

1 + 2 = 3

We have:

5 - 3 = 2

coins left, which is not enough for row 3.

So the answer is:

2

Example 2:

n = 8

We build:

1 + 2 + 3 = 6

Two coins remain:

8 - 6 = 2

which is not enough for row 4.

Answer:

3

Example 3:

n = 1

We can build one row:

1

Answer:

1

First Thought: Simulate Row by Row

We can repeatedly subtract row sizes.

Start with:

row = 1

Then:

n -= row
row += 1

until we cannot build the next row.

This works.

However, the problem has a direct mathematical structure.

Key Insight

To build k complete rows, we need:

1 + 2 + 3 + ... + k

coins.

This sum is the triangular number formula:

So we need the largest integer k such that:

This is a monotonic condition:

Because the condition changes only once from true to false, binary search works perfectly.

Algorithm

Binary search on the answer.

The number of complete rows must lie between:

0 and n

For a candidate mid, compute:

If this value is less than or equal to n, then mid complete rows are possible.

Move right to search for a larger answer.

Otherwise, move left.

At the end, return the largest valid k.

Correctness

For any integer k, the number of coins required to build k complete rows is:

This value increases as k increases.

Therefore:

So the set of valid k values forms a prefix:

valid, valid, valid, ..., invalid, invalid

Binary search correctly finds the largest valid k.

Whenever the midpoint satisfies the inequality, the answer is at least that large, so searching right preserves correctness.

Whenever the midpoint fails the inequality, the answer must be smaller, so searching left preserves correctness.

When the search ends, the returned value is the maximum number of complete rows that can be formed.

Complexity

Implementation

class Solution:
    def arrangeCoins(self, n: int) -> int:
        left = 0
        right = n

        while left <= right:
            mid = (left + right) // 2

            coins_needed = mid * (mid + 1) // 2

            if coins_needed <= n:
                left = mid + 1
            else:
                right = mid - 1

        return right

Code Explanation

We search between:

left = 0
right = n

The midpoint candidate is:

mid = (left + right) // 2

The number of coins needed for mid rows is:

implemented as:

coins_needed = mid * (mid + 1) // 2

If enough coins exist:

if coins_needed <= n:

then mid is valid, and we try larger values:

left = mid + 1

Otherwise, mid is too large:

right = mid - 1

When the loop finishes, right stores the largest valid row count.

Testing

def run_tests():
    s = Solution()

    assert s.arrangeCoins(1) == 1

    assert s.arrangeCoins(5) == 2

    assert s.arrangeCoins(8) == 3

    assert s.arrangeCoins(3) == 2

    assert s.arrangeCoins(6) == 3

    assert s.arrangeCoins(10) == 4

    assert s.arrangeCoins(0) == 0

    assert s.arrangeCoins(2147483647) == 65535

    print("all tests passed")

run_tests()

Test meaning: