#### Solution 1: Iterative Subtraction [Accepted]

**Intuition**

Given a number of coins $$n$$, we will subtract the number of coins in each row k (namely, k coins) from $$n$$ until $$n /leq 0$$. Then we count the number of subtractions we've done, and this is how many full rows we can generate.

**Algorithm**

```
class Solution:
def arrangeCoins(self, n):
"""
:type n: int
:rtype: int
"""
count = 0 ##subtractions we've performed
row = 1 ##coins in row we are subtracting
while (n >= 0):
n -= row
row += 1
count += 1
return count-1
```

This solution clearly has *O(1)* space complexity. The time complexity is a little tricky to analyze, but luckily, `count`

actually tracks the number of `while`

loops completed. We can use this:

for n = 10, `count`

= 4.

n = 100, `count`

= 13

n = 1,000, `count`

= 44

n = 10,000, `count`

= 140

We observe that each time n jumps an order of magnitude, `count`

is multiplied by approximately 3. This implies an *O(n)* time complexity.

#### Solution 2: Direct Computation [Accepted]

**Intuition**

While the above solution is most "interesting" computationally, as it solves the problem in an organic way, mathematically-inclined solvers might notice that the number of coins consumed in printing $$k$$ rows is simply the sum of integers $$1,2,3...,k$$, which by common result is $$ \frac{k(k+1)}{2} $$ (If you haven't seen this proof, it's a valuable first exercise in induction).

So we have

$$

n = \frac{k(k+1}{2}

$$

$$

2n = k^{2} + k

$$

Completing the square:

$$

2n + 0.25 = k^{2} + k + 0.25

$$

$$

2n + 0.25 = (k + 0.5)^{2}

$$

$$

\sqrt{2n + 0.25} - 0.5 = k

$$

Thus for $$n$$ coins, we can fill $$ \sqrt{2n + 0.25} - 0.5 $$ rows. We will `floor`

this to find the number of complete rows, which is done automatically by Python3's cast to `int`

.

**Algorithm**

```
class Solution:
def arrangeCoins(self, n):
"""
:type n: int
:rtype: int
"""
return int(((2*n)+0.25)**0.5 - 0.5)
```

This solution runs has *O(1)* time and space complexity.