Skip to content

441. Arranging Coins

Description

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

Solutions

Solution 1

Thinking

Row \(x\) costs \(x\) coins, so the last full row satisfies \(x(x+1)/2\le n\). Scanning \(x\) is linear and \(n\) can be \(2^{31}-1\).

The inequality solves to \(x\le \sqrt{2}\,\sqrt{n+1/8}-1/2\). Splitting \(2n\) this way avoids an overflow of \(2n\) in some languages.

A closed form evaluates in a constant number of floating-point operations.

1
2
3
class Solution:
    def arrangeCoins(self, n: int) -> int:
        return int(math.sqrt(2) * math.sqrt(n + 0.125) - 0.5)

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
using LL = long;

class Solution {
public:
    int arrangeCoins(int n) {
        LL left = 1, right = n;
        while (left < right) {
            LL mid = left + right + 1 >> 1;
            LL s = (1 + mid) * mid >> 1;
            if (n < s)
                right = mid - 1;
            else
                left = mid;
        }
        return left;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
func arrangeCoins(n int) int {
    left, right := 1, n
    for left < right {
        mid := (left + right + 1) >> 1
        if (1+mid)*mid/2 <= n {
            left = mid
        } else {
            right = mid - 1
        }
    }
    return left
}

Solution 2

Thinking

Solution 1 uses a square root; huge \(n\) can lose integer precision. Binary-search the row count with the integer test \(mid(mid+1)/2\le n\), rounding the mid upward when feasible.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def arrangeCoins(self, n: int) -> int:
        left, right = 1, n
        while left < right:
            mid = (left + right + 1) >> 1
            if (1 + mid) * mid // 2 <= n:
                left = mid
            else:
                right = mid - 1
        return left

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
    public int arrangeCoins(int n) {
        long left = 1, right = n;
        while (left < right) {
            long mid = (left + right + 1) >>> 1;
            if ((1 + mid) * mid / 2 <= n) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return (int) left;
    }
}

Comments