#### clueless coding// TODO: be smarter

Cracking the Coding Interview Elements of Programming Interviews Programming Interviews Exposed # LeetCode 441. Arranging Coins: C++ Solution

## Problem Statement

You have a total of n coins that you want to form in a staircase shape, where every k-th row must have exactly k coins.

Given n, find the total number of full staircase rows that can be formed.

n is a non-negative integer and fits within the range of a 32-bit signed integer.

``````Function Signature (C++):
int arrangeCoins(int n)

Inputs:
n = 5

Outputs:
2

We can create rows like this:
¤
¤ ¤
¤ ¤
There are 2 full rows.

Inputs:
n = 8

Outputs:
3

We can create rows like this:
¤
¤ ¤
¤ ¤ ¤
¤ ¤
There are 3 full rows.
``````

## TL;DR Code Solution

``````int arrangeCoins(int n) {

long left = 1;
long right = n;

while (left <= right) {
long middle = (left + right) / 2;
long sum = (middle * (middle + 1)) / 2.0;

if (sum < n) {
left = middle + 1;
}
else if (sum > n) {
right = middle - 1;
}
else {
return middle;
}
}

return left - 1;

}

``````