441. Arranging Coins

Problem Description

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 <= 2³¹ - 1

Python Solution

class Solution:
    def arrangeCoins(self, n: int) -> int:
        # Using binary search
        left, right = 1, n
        
        while left <= right:
            mid = (left + right) // 2
            coins = (mid * (mid + 1)) // 2
            
            if coins == n:
                return mid
            elif coins < n:
                left = mid + 1
            else:
                right = mid - 1
        
        return right

Java Solution

class Solution {
    public int arrangeCoins(int n) {
        // Using binary search
        long left = 1, right = n;
        
        while (left <= right) {
            long mid = left + (right - left) / 2;
            long coins = (mid * (mid + 1)) / 2;
            
            if (coins == n) {
                return (int)mid;
            } else if (coins < n) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return (int)right;
    }
}

C++ Solution

class Solution {
public:
    int arrangeCoins(int n) {
        // Using binary search
        long left = 1, right = n;
        
        while (left <= right) {
            long mid = left + (right - left) / 2;
            long coins = (mid * (mid + 1)) / 2;
            
            if (coins == n) {
                return mid;
            } else if (coins < n) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return right;
    }
};

JavaScript Solution

/**
 * @param {number} n
 * @return {number}
 */
var arrangeCoins = function(n) {
    // Using binary search
    let left = 1, right = n;
    
    while (left <= right) {
        const mid = Math.floor(left + (right - left) / 2);
        const coins = Math.floor((mid * (mid + 1)) / 2);
        
        if (coins === n) {
            return mid;
        } else if (coins < n) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return right;
};

C# Solution

public class Solution {
    public int ArrangeCoins(int n) {
        // Using binary search
        long left = 1, right = n;
        
        while (left <= right) {
            long mid = left + (right - left) / 2;
            long coins = (mid * (mid + 1)) / 2;
            
            if (coins == n) {
                return (int)mid;
            } else if (coins < n) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return (int)right;
    }
}