You have n coins and you want to build a staircase with these coins. The staircase consists of k rows where the ith row has exactly i coins. The last row of the staircase may be incomplete.
Given the integer n, return the number of complete rows of the staircase you will build.
Example 1:
Input: n = 5
Output: 2
Explanation: Because the 3rd row is incomplete, we return 2.
Example 2:
Input: n = 8
Output: 3
Explanation: Because the 4th row is incomplete, we return 3.
Constraints:
- 1 <= n <= 231 - 1
My Solution
We can solve this problem with binary search. We start with our start pointer equal to 1 and our end pointer equal to n. We find the midpoint between end and start at every iteration and check whether mid*(mid+1)/2 is equal to n, in which case it completely fills mid rows. If it is equal to n, we return mid. Otherwise if it is less than n, we make start equal to mid+1. If is greater than n, we make end equal to mid-1. Finally in the case of an incomplete row, we end with end pointing to the maximum number of complete rows. One detail is to ensure that we use longs for start, end and mid due to potential integer overflow, due to the constraints.
Time complexity is O(log n) due to binary search. Space complexity is O(1) because we only use constant extra space.
class Solution {
public int arrangeCoins(int n) {
long start = 1;
long end = n;
while (start <= end) {
long mid = start + (end-start)/2;
if (mid*(mid+1)/2 == n) {
return (int)mid;
}
else if (mid*(mid+1)/2 < n) {
start = mid+1;
}
else {
end = mid-1;
}
}
return (int)end;
}
}