Arranging Coins

Problem

You have n coins to arrange in a staircase where row i has i coins. Return the largest k such that the first k rows are completely filled.

Constraints

• 1 ≤ n ≤ 2³¹−1

Approach — Binary Search

This is a Binary Search problem. The idea: repeatedly halve the search space, discarding the half that can't contain the answer. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(log n) time.

Solution code

Python

class Solution:
    def arrangeCoins(self, n):
        k = 0
        while n >= k + 1:
            k += 1
            n -= k
        return k

Java

class Solution {
    public int arrangeCoins(int n) {
        long lo = 0, hi = n;
        while (lo <= hi) {
            long m = lo + (hi - lo) / 2;
            long need = m * (m + 1) / 2;
            if (need == n) return (int)m;
            if (need < n)  lo = m + 1;
            else            hi = m - 1;
        }
        return (int)hi;
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.