## 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.