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

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)

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.

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)

True
True
True
True
True
True


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.