algoadvance

Leetcode 441. Arranging Coins

Problem Statement

You have (n) coins, and you want to build a staircase with them. The staircase consists of (k) rows where the (i)-th row has exactly (i) coins. The last row of the staircase may be incomplete if there are not enough coins.

Given the integer (n), return the number of complete rows of the staircase you will be able to form.

Example

Clarifying Questions

  1. Can (n) be zero?
    • Yes, in which case no rows can be formed.
  2. What is the maximum value of (n)?
    • For this specific problem, (n) can be as large as (2^{31} - 1).

Strategy

We need to find the maximum number of complete rows that can be formed with the given number of coins, (n). This problem can be solved using a mathematical approach by recognizing the sequence of rows:

  1. The total number of coins required to fill (k) rows is given by the sum of the first (k) natural numbers: [ S = \frac{k \times (k + 1)}{2} ]
  2. We need to find the largest (k) such that: [ \frac{k \times (k + 1)}{2} \leq n ]
  3. This can be solved using binary search to find the optimal (k).

Code

#include <iostream>
using namespace std;

class Solution {
public:
    int arrangeCoins(int n) {
        long left = 0, right = n; // using long to handle large values
        while (left <= right) {
            long mid = left + (right - left) / 2;
            long curr = mid * (mid + 1) / 2;
            if (curr == n) {
                return mid;
            } else if (curr < n) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return right; // When left > right, right is the largest k such that k*(k+1)/2 <= n
    }
};

int main() {
    Solution solution;
    int n;
    cout << "Enter the number of coins: ";
    cin >> n;
    cout << "Number of complete rows: " << solution.arrangeCoins(n) << endl;
    return 0;
}

Time Complexity

The time complexity of the above solution is (O(\log n)) because we are using binary search to determine the maximum number of complete rows. The space complexity is (O(1)) as we are using a constant amount of extra space.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI