How do you approach Arranging Coins?

k complete rows use exactly k * (k + 1) / 2 coins (the k-th triangular number).

What is the time complexity of Arranging Coins?

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

What are common mistakes on Arranging Coins?

Computing the midpoint as (low + high) / 2. In a fixed-width integer language that overflows on large ranges; low + (high - low) / 2 does not. An update that fails to shrink the range, which spins forever on a two-element window. Answering "does it exist" when the question asked for the first or last occurrence - the boundary variants need a different post-loop return.

gitGood.dev

← Back to problems

Arranging Coins

EasyAlgorithms

Description

You have n coins and you want to build a staircase with them. The staircase consists of k rows where the i-th row has exactly i coins. The last row of the staircase may be incomplete.

Given the integer n, return the number of complete rows of the staircase you will build.

Example 1

Input: n = 5

Output: 2

Explanation: Rows of 1 and 2 coins are complete (3 coins used); the third row only gets 2 of the 3 coins it needs.

Example 2

Input: n = 8

Output: 3

Explanation: Rows 1, 2, 3 use 6 coins; the fourth row gets only 2 of 4.

Example 3

Input: n = 1

Output: 1

Constraints

- 1 <= n <= 2^31 - 1

Arranging Coins: approach, complexity and pitfalls

An easy binary search problem, graded against 7 test cases (4 of them hidden).

The pattern: Binary Search

Halving a search space each step - on sorted arrays, and on answers themselves.

Reach for it when you see: A sorted input, or a monotonic "is this value feasible?" predicate you can binary search over.

If you are stuck

Show the 3-step hint ladder

k complete rows use exactly k * (k + 1) / 2 coins (the k-th triangular number).
You need the largest k with k * (k + 1) / 2 <= n. The triangular numbers are sorted - which technique finds a boundary in a sorted sequence?
Binary search k in [0, 65536): if mid * (mid + 1) / 2 <= n move the lower bound up, otherwise shrink the upper bound.

The optimal approach

Show the approach: Binary Search on the Row Count

The first `k` rows consume the triangular number `k(k+1)/2`, a strictly increasing function of `k`. Binary search for the largest `k` whose triangular number still fits within `n`. Since `n < 2^31`, `k` never exceeds 65535, so the intermediate product stays far below any precision limits.

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

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

Common Binary Search mistakes

These apply to the pattern as a whole, not just this problem.

Computing the midpoint as `(low + high) / 2`. In a fixed-width integer language that overflows on large ranges; `low + (high - low) / 2` does not.
An update that fails to shrink the range, which spins forever on a two-element window.
Answering "does it exist" when the question asked for the first or last occurrence - the boundary variants need a different post-loop return.