Skip to main content

441. Arranging Coins

easy

Given n coins, arrange them in a staircase where the k-th row has exactly k coins, and return the count of complete rows. A triangular-number inverse — solvable by binary search or closed form via the quadratic formula.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

You have a total of n coins that you want to form in a staircase shape, where every k-th row must have exactly k coins. Given n, find the total number of full staircase rows that can be formed. n is a non-negative integer and fits within the range of a 32-bit signed integer.

Constraints

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

Examples

Example 1

Input
n = 5
Output
2

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

Example 2

Input
n = 8
Output
3

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

k complete rows use 1 + 2 + ... + k = k * (k + 1) / 2 coins. Find the largest k with k * (k + 1) / 2 <= n.

Hint 2

Simulation: subtract 1, then 2, ... until you can't. O(sqrt(n)) iterations.

Hint 3

Binary search lo = 1, hi = n. Check mid * (mid + 1) / 2 <= n. O(log n) time.

Hint 4

Closed form: solve k^2 + k - 2n = 0 to get k = (-1 + sqrt(1 + 8n)) / 2. Return floor(k). Be careful with floating-point precision near boundary values.

Solution approach

Reveal approach

Binary search the largest k satisfying k * (k + 1) / 2 <= n. lo = 1, hi = n, answer = 0. While lo <= hi: mid = lo + (hi - lo) / 2. Compute coins = mid * (mid + 1) / 2 (use 64-bit to avoid overflow for large n). If coins <= n, answer = mid and lo = mid + 1; else hi = mid - 1. Return answer. O(log n) time, O(1) space. Closed-form alternative: floor((-1 + sqrt(1 + 8 * n)) / 2), but use long double or integer-checking afterward to avoid floating-point errors at boundary inputs near 2^31. The binary search is more interview-friendly because it side-steps any precision argument.

Complexity

Time
O(log n)
Space
O(1)

Related patterns

  • binary-search
  • math

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Apple

More Math practice problems

See all Math problems →