[LeetCode] Problem 441 - Arranging Coins

Posted on | In ,

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.

Example

No.1

n = 5

The coins can form the following rows:

1
2
3
¤
¤ ¤
¤ ¤

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

No.2

n = 8

The coins can form the following rows:

1
2
3
4
¤
¤ ¤
¤ ¤ ¤
¤ ¤

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

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int arrangeCoins(int n) {
    if (n <= 1)
        return n;
    
    long left = 1;
    long right = n;

    while (left < right) {
        long mid = left + (right - left) / 2;

        if (mid * (mid + 1) / 2 > n)
            right = mid;
        else
            left = mid + 1;
    }

    return (int) left - 1;
}