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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Arranging Coins and Math problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →