Question One - Arrange Coins

You have a total of n coins that you want to form in a staircase shape, where every k-th row must have exactly k coins.

Given n, find the total number of full staircase rows that can be formed.

n is a non-negative integer and fits within the range of a 32-bit signed integer.

Example 1

n = 5

The coins can form the following rows:
¤
¤ ¤
¤ ¤

Because the 3rd row is incomplete, we return 2.

Example 2

n = 8

The coins can form the following rows:
¤
¤ ¤
¤ ¤ ¤
¤ ¤

Because the 4th row is incomplete, we return 3.

Solution

/**
 * @param {number} n
 * @return {number}
 */
var arrangeCoins = function(n) {
    var fullRows = 0;
    var coinsToPlace = 1;
    while(n > 0){
      n = n - coinsToPlace;
      if(n >= 0){
        fullRows++;
        coinsToPlace++;
      }
    }
    return fullRows;
};

Discussion

For this question, I took some time to think about the best way to implement a solution. I tried a couple of times using a for loop but I kept reaching a point where I said to myself that my solution wasn't going to work. After running through a couple scenarios in my head, I came up with the following solution in psuedo-code.

1. Place one coin on the table
2. Decrease the total number of coins that I had remaining by one
3. If I still have coins remaining, increase the total number of complete rows by one and increase the number of coins I would place on the table for the next row by one

My first row has one coin, so for my next row, I have to -

1. Place two coins on the table
2. Decrease the totol number of coins I had remaining by two
3. If I still have coins remaining, increase the total number of complete rows by one and increase the number of coins I would place on the table for the next row by one

I continue this process until I have no more coins remaining.

Let's see how we implement this using code -

/**
 * @param {number} n
 * @return {number}
 */
var arrangeCoins = function(n) {
    var fullRows = 0;
    var coinsToPlace = 1;
}

We initialize fullRows as 0 and the coinsToPlace as 1. coinsToPlace is defined as 1 because we always place one coin on the table first.

/**
 * @param {number} n
 * @return {number}
 */
var arrangeCoins = function(n) {
    var fullRows = 0;
    var coinsToPlace = 1;
    while(n > 0){
      n = n - coinsToPlace;
    }
    return fullRows;
};

Our while loop implements the condition that we must repeat the action until the number of coins we have remaining is less than or equal to 0.

n = n - coinsToPlace;

The line above implements our decrease in remaining coins. For example, if we started with 5 coins, on our first loop, we'd subtract one and have 4 remaining.

/**
 * @param {number} n
 * @return {number}
 */
var arrangeCoins = function(n) {
    var fullRows = 0;
    var coinsToPlace = 1;
    while(n > 0){
      n = n - coinsToPlace;
      if(n >= 0){
        fullRows++;
        coinsToPlace++;
      }
    }
    return fullRows;
};

Finally, we have an if statement within our while loop that implements the third condition in our psuedocode. We say -

• If n > 0 i.e. if I still have coins remaining.
• fullRows++ increase the number of full rows we have by one.
• coinsToPlace++ increase the number of coins I have to place on the table next by one.

We repeat the process until n - coinsToPlace results in a number equal to or below 0 then we return the number of full rows.