Arranging Coins

This problem asks you to find how many full rows can be formed in a staircase pattern using n coins. A direct simulation is inefficient for large n, so the optimal approach is to perform a binary search over the possible number of rows. By checking the total coins required for a candidate row count, you can quickly narrow down the correct number of complete rows and handle large values without overflow.

Problem Statement

You have a total of n coins and want to arrange them into a staircase shape. Each row i must contain exactly i coins. The staircase may have a partially completed last row.

Given an integer n, return the number of complete rows that can be formed. For example, if n = 5, the staircase rows would be [1,2,2], and the answer is 2 because the third row is incomplete.

Examples

Example 1

Input: n = 5

Output: 2

Because the 3rd row is incomplete, we return 2.

Example 2

Input: n = 8

Output: 3

Because the 4th row is incomplete, we return 3.

Constraints

• 1 <= n <= 231 - 1

Solution Approach

Mathematical Summation Check

Use the formula for the sum of the first k natural numbers, k*(k+1)/2, to check if k rows can be fully formed. Increment k until the total exceeds n. This approach directly ties to the problem's staircase pattern but is slower for very large n.

Binary Search Over Row Count

Set low = 0 and high = n, and perform binary search to find the largest k where k*(k+1)/2 <= n. Adjust mid and narrow the search based on whether the total coins fit. This uses the primary pattern of binary search over the answer space, avoiding iterative summation.

Quadratic Formula Optimization

Solve k*(k+1)/2 <= n directly using the quadratic formula: k = floor((-1 + sqrt(1 + 8*n)) / 2). This provides an O(1) solution, but it requires careful handling of integer precision and is prone to overflow if not implemented properly.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity ranges from O(log n) for binary search to O(1) for the quadratic formula solution. Space complexity is O(1) for all approaches since no additional data structures are required.

What Interviewers Usually Probe

• Asks for a solution that scales beyond naive iteration
• Hints at using math formulas to check row completion
• Checks if candidate considered binary search over row numbers

Common Pitfalls or Variants

Common pitfalls

• Off-by-one errors when counting complete rows
• Overflow when computing k*(k+1)/2 for large n
• Confusing total coins with row index, leading to incorrect binary search bounds

Follow-up variants

• Return the total number of coins used in complete rows instead of row count
• Find the first incomplete row's index
• Compute the minimum n required to form exactly k complete rows

FAQ

What is the main strategy to solve Arranging Coins efficiently?

Use binary search over the number of rows or the quadratic formula to find the maximum k such that k*(k+1)/2 <= n.

Why not simply iterate row by row?

Iterating row by row is inefficient for large n and may exceed time limits; binary search or formula approaches scale properly.

How do I handle large n without overflow?

Use long integers or carefully apply the quadratic formula to avoid k*(k+1)/2 exceeding integer limits.

Can this problem be solved in O(1) time?

Yes, applying the quadratic formula directly computes the maximum complete rows in constant time.

How does the binary search pattern apply here?

Binary search checks candidate row counts against the total coins, efficiently narrowing down the largest valid number of complete rows.