public int arrangeCoins(int n) {
//convert int to long to prevent integer overflow
long nLong = (long)n;
long st = 0;
long ed = nLong;
long mid = 0;
while (st <= ed){
mid = st + (ed  st) / 2;
if (mid * (mid + 1) <= 2 * nLong){
st = mid + 1;
}else{
ed = mid  1;
}
}
return (int)(st  1);
}
O(logn) binary search java solution


@BalabalaXing
Our target is to search for a factor k where k * (k+1) / 2 <= n. This is referencing Gauss' formula on summation of consecutive numbers.
Using binary search for such purpose gives you O(log n) time.
