441 Arranging Coins

1. 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 case you will build.

Constraints: \(1 \leq n \leq 2^{31} - 1\)

1.1. Examples:

1
11
11

Input: n = 5
Output: 2
Explanation: Because the 3rd row is incomplete, we return 2.


1
11
111
11

Input: n = 8
Output: 3
Explanation: Because the 4th row is incomplete, we return 3.

2. Solution

2.1. Understanding the problem

I think this question is equivalent to the fowllowing question: \(\frac{(1+i)i}{2} \leq n \leq \frac{(1+i+1)(i+1)}{2}, \text{ solve i}\)

2.2. Algorithm

We can solve the left part of the inequation and get i. \(i = \lfloor{\sqrt{2n+\frac{1}{4}} - \frac{1}{2}}\rfloor\)

2.3. Code

Listing 1: 441 Arranging Coins my solution

import math

def arrangeCoins(n: int):
    return int(math.floor(math.sqrt(2 * n + 0.25) - 0.5))

print(arrangeCoins(5) == 2)
print(arrangeCoins(8) == 3)
print(arrangeCoins(1) == 1)
print(arrangeCoins(2) == 1)
print(arrangeCoins(3) == 2)
print(arrangeCoins(4) == 2)

Listing 2: 441 Arranging Coins my solution-results

True
True
True
True
True
True

2.3.1. Complexity

2.3.1.1. Time complexity:

O(1) because there is an upper bound of the time required.

2.3.1.2. Space complexity:

O(1) because there is an upper bound of the space required.

2.4. Leetcode solution

Leetcode uses two solutions (Binary Search and math), and I'm glad that the second one is exactly my solution, good job Leetcode :)!

As an exercise, I implement the binary search solution here but I don't really like binary search in general because there are too many edge cases to consider, i.e. starting/ending numbers, mid point…

As we have established in 2.1, \(\frac{(1+i)i}{2} \leq n\), this means we want to search for an i in 1...n that satisfies the condition.

Listing 3: 441 Arranging Coins leetcode solution

def arrangeCoins(n: int):
    # how do we know that left should start from 0?
    # this is why I don't want to use binary search
    left, right = 0, n
    while left <= right:
        mid = (left + right) // 2

        temp = mid * (mid + 1) // 2
        if temp == n:
            return mid
        if temp > n:
            right = mid - 1
        if temp < n:
            left = mid + 1
    return right


print(arrangeCoins(5) == 2)
print(arrangeCoins(8) == 3)
print(arrangeCoins(1) == 1)
print(arrangeCoins(2) == 1)
print(arrangeCoins(3) == 2)
print(arrangeCoins(4) == 2)

Listing 4: 441 Arranging Coins leetcode solution-results

True
True
True
True
True
True

2.4.1. Time complexity:

2.4.2. Space complexity:

3. More analysis

3.1. General thoughts

Binary Search is hard in the sense that it requires a great amount of attention to edge cases. I think I'll have to spend more time on it to get the hang of it.