# 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

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

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