Arranging Coins

Problem Statement

Consider you have been given a set number of coins, and you wish to arrange these into a staircase structure. The rules mandate that each subsequent row in this staircase contains one more coin than the previous row. This results in the first row containing one coin, the second row two coins, and so on. You hope to continue this pattern until you cannot complete a full row with the remaining coins. The task at hand is to determine the total number of complete rows that you can form with the provided coins.

Examples

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 <= 231 - 1

Approach and Intuition

The main challenge is to figure out how many complete rows we can form with the given set of coins, adhering to the increment rule.

1. An intuitive way to solve this involves using a running sum that tracks the number of coins used till each row.
2. Start from the first row and for each row, if you have enough coins to complete the row, you add more coins to fulfill the next row's requirement.
3. Continuously subtract the coins needed for the current row from the total coins.
4. When you reach a point where you do not have enough coins to complete the next row, you stop and count the number of completed rows.

For accomplishing this iteratively:

1. Initialize a running sum and a count of rows.
2. Start incrementing row by row; for each row i, check if you can subtract i coins from your running total without going negative.
3. If yes, proceed to the next row after subtracting the coins. If no, your loop ends, and the total rows count is your answer.

The examples given (5 coins, and 8 coins) can be solved as follows:

• For n = 5:
  • Row 1 needs 1coin: 5 - 1 = 4 (Valid)
  • Row 2 needs 2 coins: 4 - 2 = 2 (Valid)
  • Row 3 needs 3 coins: 2 - 3 = -1 (Invalid)
  • Total complete rows = 2.
• For n = 8:
  • Row 1 needs 1 coin: 8 - 1 = 7 (Valid)
  • Row 2 needs 2 coins: 7 - 2 = 5 (Valid)
  • Row 3 needs 3 coins: 5 - 3 = 2 (Valid)
  • Row 4 needs 4 coins: 2 - 4 = -2 (Invalid)
  • Total complete rows = 3.

This method efficiently calculates the number of rows by simply iterating through each potential row and checking the feasibility based on remaining coins. The solution can be implemented in a time complexity of O(k), where k is the number of complete rows we can form.

Solutions

class Solution {
  public int countStairs(int total) {
    return (int)(Math.sqrt(2 * (long)total + 0.25) - 0.5);
  }
}