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