algoadvance

Leetcode 441. Arranging Coins

Problem Statement

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 contains exactly i coins. The last row of the staircase may not be complete.

Given a number n, find the total number of complete rows of the staircase you can form.

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.

Clarifying Questions

1. Is n always non-negative?
   • Yes, n is always a non-negative integer.
2. What is the maximum value of n?
   • The problem does not specify, but assume it can fit within the range of a 32-bit signed integer.
3. Should the solution handle large values of n efficiently?
   • Yes, the solution should be efficient even for large values of n.

Strategy

To determine the number of complete rows, we need to sum the series: 1 + 2 + 3 + … + k. The sum of the first k natural numbers is given by the formula:

[ S = \frac{k(k + 1)}{2} ]

We need to find the maximum k such that:

[ \frac{k(k + 1)}{2} \leq n ]

This optimal strategy to find k is to use binary search:

1. Initialize two variables left set to 0 and right set to n.
2. While left is less than or equal to right:
   • Compute the middle point mid.
   • Calculate current = mid * (mid + 1) / 2.
   • If current is equal to n, then return mid.
   • If current is less than n, move the left boundary to mid + 1.
   • If current is greater than n, move the right boundary to mid - 1.
3. Return right.

Code

public class Solution {
    public int arrangeCoins(int n) {
        if (n == 0) return 0; // Edge case for n = 0
        int left = 0, right = n;
        while (left <= right) {
            int mid = left + (left - right) / 2;
            long current = (long) mid * (mid + 1) / 2;

            if (current == n) {
                return mid;
            } else if (current < n) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return right;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.arrangeCoins(5)); // Output: 2
        System.out.println(solution.arrangeCoins(8)); // Output: 3
    }
}

Time Complexity

• Time Complexity: The binary search reduces the problem size by half at each step, making the time complexity O(log n).
• Space Complexity: The space complexity is O(1) because we are using a constant amount of extra space.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?