Arranging Coins Problem
Description
LeetCode Problem 441.
You have n coins and you want to build a staircase with these coins. The staircase consists of k rows where the i^th 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:
1
2
3
Input: n = 5
Output: 2
Explanation: Because the 3^rd row is incomplete, we return 2.
Example 2:
1
2
3
Input: n = 8
Output: 3
Explanation: Because the 4^th row is incomplete, we return 3.
Constraints:
- 1 <= n <= 2^31 - 1
Sample C++ Code using Binary Search
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
int arrangeCoins(int n) {
int l = 1, r = n, ans;
long rows, coinsNeeded;
while (l <= r) {
rows = l + ((r-l) >> 1); // finding mid of range [l, r]
coinsNeeded = (rows * (rows + 1)) >> 1; // coins needed for 'rows' number of row
if (coinsNeeded <= n)
l = rows + 1, ans = rows; // if available coins are sufficient
else r = rows - 1; // coins insufficient, eliminate the half greater than rows
}
return ans;
}
};