Arranging Coins

Arranging Coins

Arranging Coins is a problem where you need to arrange coins in the form of a staircase pattern. The problem statement goes like this:

You have n coins and you want to build a staircase with these coins. The staircase consists of rows of coins where each row has one more coin than the previous row. The last row of the staircase may be incomplete.

For example, if you have 5 coins, the staircase will look like this:

      o
     o o
    o o o
   o o
  o

The question you need to answer is: what is the maximum height of the staircase that can be built with these coins?

Solution

There are multiple ways to solve this problem, but one simple way is to use a loop and keep track of the number of coins used so far. Here's how you can do it:

function arrangeCoins(n) {
  let i = 1;
  while (n >= i) {
    n -= i;
    i++;
  }
  return i - 1;
}

console.log(arrangeCoins(5)); // Output: 2

In this solution, we start with the first row which has one coin, and keep adding rows until we run out of coins. We subtract the number of coins used in each row from the total number of coins left. Finally, we return the number of rows that were built.

Another way to solve this problem is to use a formula. The formula for the sum of the first n natural numbers is:

sum = n * (n + 1) / 2

We can use this formula to find the maximum height of the staircase. We can solve for n in the equation n * (n + 1) / 2 = coins, and take the floor of the result. Here's how you can do it:

function arrangeCoins(n) {
  return Math.floor((-1 + Math.sqrt(1 + 8 * n)) / 2);
}

console.log(arrangeCoins(5)); // Output: 2

In this solution, we use the quadratic formula to solve for n. We take the positive root and take the floor of the result to get the maximum height of the staircase.

Conclusion

Arranging Coins is a simple problem that can be solved using a loop or a formula. Both solutions are efficient and have a time complexity of O(sqrt(n)).