# C++ 1 line code

• Let me know if anyone need explanation :)

``````int arrangeCoins(int n) {
return (int)floor((long long)(floor(sqrt(1LL + 8LL * n)) - 1LL) >> 1LL);
}
``````

• A slightly easier to understand version would be

``````return (int(sqrt((8*(long long)n+1)))-1)/2;
``````

Here comes the explanation:
First lets define `Nk` as a function return n coins of full stairs with height k .
i.e.

``````N3=6;
N4=10;
``````

We know that

``````Nk=(k+1)*k/2;
``````

solve this equation we will get

``````k=((8Nk+1)^(0.5)-1)/2;
``````

because from Nk=(k+1)*k/2

``````    2Nk = k^2+k
``````

then

``````    8Nk = 4*k^2+4*k

``````

then

``````    8Nk+1 = (2k+1)^2;
``````

then

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

to use `n` instead of `Nk`

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

Finally if you use

``````return (int(sqrt((8*n+1)))-1)/2;
``````

You will find there are some test cases with very large `n` such that `8*n` would overflow, then you will using
`long long` to prevent overflow.

end of in the end
using right shift `>>1` instead of `/2`.

Thanks `kaidul`, you idea is exactly same with me. :P

• Thanks cdrover

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.