LeetCode 441: Arranging Coins Solution

Problem Explanation

Explanation

To solve this problem, we can use a binary search approach. We know that the total number of coins needed to build a staircase with k rows is given by the formula 1 + 2 + ... + k = k * (k + 1) / 2. We can use binary search to find the maximum number of complete rows that can be built with n coins.

Initialize left as 0 and right as n.
Perform binary search to find the maximum number of complete rows.
Calculate the total coins needed for mid rows using the formula.
Compare the total coins with n and adjust the search space accordingly.

The time complexity of this approach is O(log n) and the space complexity is O(1).

Solution Code

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

Frequently Asked Questions

How to solve LeetCode 441 (Arranging Coins)?

This page provides optimized solutions for LeetCode problem 441 (Arranging Coins) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 441 (Arranging Coins)?

The time complexity for LeetCode 441 (Arranging Coins) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 441 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 441 in Java, C++, or Python.

441. Arranging Coins