Scale Engineer

Arranging Coins

Easy
#0428Time: O(log n). The binary search algorithm halves the search space in each iteration. The search space is from 1 to `n`.Space: O(1). We only use a constant number of variables for the binary search pointers and result.
Patterns
Math
Algorithms
Binary Search

Prompt

You have n coins and you want to build a staircase with these coins. The staircase consists of k rows where the ith 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: 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.

 

Constraints:

  • 1 <= n <= 231 - 1

Approaches

3 approaches with complexity analysis and trade-offs.

A more efficient approach is to use binary search. We know that the number of coins required for k complete rows is 1 + 2 + ... + k = k * (k + 1) / 2. This is a monotonically increasing function of k. We can use binary search to find the largest k for which this sum is less than or equal to n.

Algorithm

    1. Initialize left = 1, right = n, and result = 0.
    1. While left <= right:
    1. Calculate mid = left + (right - left) / 2. Use long to prevent overflow.
    1. Calculate the coins needed for mid rows: coinsNeeded = mid * (mid + 1) / 2.
    1. If coinsNeeded <= n:
    • mid is a potential answer. Store it: result = mid.
    • Search for a larger k: left = mid + 1.
    1. Else (coinsNeeded > n):
    • mid is too large. Search for a smaller k: right = mid - 1.
    1. Return result.

Walkthrough

The problem asks for the largest integer k such that the sum of coins S_k = k * (k + 1) / 2 does not exceed n. Since S_k increases as k increases, we can efficiently search for k in the range [1, n]. We set up a binary search with left and right pointers. For each mid value, we calculate the coins needed, mid * (mid + 1) / 2. If the coins needed are less than or equal to n, it means mid could be our answer, and we should try for a larger k. So, we record mid and move our search to the right half (left = mid + 1). If the coins needed are more than n, mid is too large, and we must search in the left half (right = mid - 1). It's crucial to use long for intermediate calculations to avoid integer overflow, as n can be large.

class Solution {    public int arrangeCoins(int n) {        long left = 1, right = n;        long result = 0;        while (left <= right) {            long mid = left + (right - left) / 2;            long coinsNeeded = mid * (mid + 1) / 2;            if (coinsNeeded <= n) {                result = mid;                left = mid + 1;            } else {                right = mid - 1;            }        }        return (int) result;    }}

Complexity

Time

O(log n). The binary search algorithm halves the search space in each iteration. The search space is from 1 to `n`.

Space

O(1). We only use a constant number of variables for the binary search pointers and result.

Trade-offs

Pros

  • Significantly faster than the brute-force approach.

  • Guaranteed to find the solution within logarithmic time.

Cons

  • Slightly more complex to implement than the linear scan.

  • Requires careful handling of potential integer overflows by using long.

Solutions

class Solution { public int arrangeCoins ( int n ) { return ( int ) ( Math . sqrt ( 2 ) * Math . sqrt ( n + 0.125 ) - 0.5 ); } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem