# C++ Three solutions: O(n), O(logn), O(1)

• ``````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;
}
};
``````

• The first solution I think it is O(sqrt(n)). Correct me if I am wrong. Thx!

• @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.

• This post is deleted!

• @DragonJ Yes, you are correct.

• ``````long mid = low + (high - low + 1) / 2;
``````

Why do we need the + 1 here, without +1, we will get Time Exceed Limit. Can anyone help me understand the corner case about that?
I assume there is something related to the stopping condition `while (low < high)`

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