Given a total of `n`

coins find the total number of full staircase rows that can be built.

Staircase rows are those where `i`

-th row has `i`

coins.

For example, given n = 6, return 3 as you can form staircase like this:

```
*
* *
* * *
```

Given n = 9, return 3.

```
*
* *
* * *
* * *
```

Note that, the 4th row is invalid as it doesn't have 4 coins.

## Approach - 1: Binary Search

To build a staircase till k-th row, we need:

1 + 2 + 3 + ... + k = k*(k + 1) / 2 coins.

So we need to find maximum k such that, k*(k + 1) / 2 <= n.

Since n is an increasing function of k, we can use binary search to solve this problem.

We initialize `low`

and `high`

as `0`

and `n`

respectively. In each step, we calculate

the value of coins required using the formula n = k*(k + 1) / 2 where `k`

is the

middle element between `low`

and `high`

. If the required coins are greater than

`n`

the value of `high`

is updated to `k - 1`

and if its less than `n`

, the value

of `low`

is updated to `k + 1`

. Since we reduce the search space by half at each

iteration, the time complexity is `O(logN)`

, where N is the number of coins.

C++ code:

```
#include <iostream>
using namespace std;
int arrangeCoins(int n) {
long low = 0, high = n;
while (low <= high) {
long k = low + (high - low) / 2;
long cur = k * (k + 1) / 2;
if (cur == n) return (int)k;
if (n < cur) {
high = k - 1;
} else {
low = k + 1;
}
}
return (int)high;
}
int main() {
cout << 6 << " " << arrangeCoins(6) << endl;
cout << 9 << " " << arrangeCoins(9) << endl;
}
```

Python code:

```
def arrangeCoins(n):
low = 0
high = n
while low <= high:
k = low + (high - low) // 2
cur = k * (k + 1) // 2
if cur == n: return k
if n < cur:
high = k - 1
else:
low = k + 1
return high
if __name__ == '__main__':
print(6, arrangeCoins(6)) # n = 6, prints 3
print(9, arrangeCoins(9)) # n = 9, prints 3
```

Time Complexity: `O(logN)`

due to binary search

Space Complexity: `O(1)`

## Approach - 2: Math

We have formulated the equation:

```
k*(k + 1) / 2 <= n
k^2 + k <= 2*n
k^2 + k - 2*n <=0
```

We can use Sridharacarya's formula to solve this equation:

```
k = (-1 + sqrt(1 + 8n))/2
```

C++ code:

```
#include <iostream>
#include <cmath>
using namespace std;
int arrangeCoins(int n) {
int(-1 + sqrt(1 + (long)8 * n)) / 2;
}
int main() {
cout << 6 << " " << arrangeCoins(6) << endl;
cout << 9 << " " << arrangeCoins(9) << endl;
}
```

Python code:

```
def arrangeCoins(n):
return int((-1 + ((1 + 8 * n) ** 0.5)) / 2)
if __name__ == '__main__':
print(6, arrangeCoins(6)) # n = 6, prints 3
print(9, arrangeCoins(9)) # n = 9, prints 3
```

Time Complexity: `O(1)`

Space Complexity: `O(1)`

## Top comments (4)

Nice article 😃

I have one suggestion if you want your C++ solution to be more performant, you can use the keyword

`constexpr`

and have your function`arrangeCoins`

to be executed at compile Time 😉Thanks! I will look into it more!

This is just a simple high-school algebra problem. People really ask this in programming interviews?

If I were asking someone this, I'd react pretty negatively to the binary-search solution -- any competent engineer should realize there's a simple closed-form solution.

It's an easy question though. Can be asked in phone screen or as a warm up question.