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


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




Related Posts

Super Egg Drop Problem

LeetCode 887. You are given k identical eggs and you...

Peak Index In A Mountain Array Problem

LeetCode 852. Let’s call an array arr a mountainif the...

Numbers At Most N Given Digit Set Problem

LeetCode 902. Given an array of digits which is sorted...

Nth Magical Number Problem

LeetCode 878. A positive integer is magical if it is...

Koko Eating Bananas Problem

LeetCode 875. Koko loves to eat bananas. There are n...