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

Find K-Th Smallest Pair Distance Problem

LeetCode 719. The distance of a pair of integers a...

Binary Search Problem

LeetCode 704. Given an array of integers nums which is...

Random Point In Non-Overlapping Rectangles Problem

LeetCode 497. You are given an array of non-overlapping axis-aligned...

Split Array Largest Sum Problem

LeetCode 410. Given an array nums which consists of non-negative...

Smallest Good Base Problem

LeetCode 483. Given an integer n represented as a string,...

Single Element In A Sorted Array Problem

LeetCode 540. You are given a sorted array consisting of...