class Solution {
public:
int way1(int n) {
int level = 1;
for (long sum = 0; sum <= n; level++)
sum += level;
return max(level  2, 0);
}
int way2(int n) {
return sqrt(2 * (long)n + 1 / 4.0)  1 / 2.0;
}
int arrangeCoins(int n) {
long low = 1, high = n;
while (low < high) {
long mid = low + (high  low + 1) / 2;
if ((mid + 1) * mid / 2.0 <= n) low = mid;
else high = mid  1;
}
return high;
}
};
C++ Three solutions: O(n), O(logn), O(1)


@DragonJ I think the author means O(k), O(1), O(log(k)), where k is the number of staircases. In fact k is of order O(log(n)), so technically you are correct.

@Zach_Shi No. With n the author means, the number of coins, not the number of possible stairs.
