LeetCode July Challenge -1: ArrangeCoins -solution explained

Question : 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.

Refer the problem here

---

Solution:

We can solve this problem in 3 different ways.

Basically, the main idea to solve this problem is same for all 3 approaches. If you observe carefully, for each row K is in increasing order.

Brute Force approach:

1. Lets start by taking k = 0 and then continue linearly.
2. increment k by 1 and decrement k coins from n
3. loop until n value is greater than 0.

let arrangeCoins = function (n) {
  let k = 0;
  while (n > 0) {
    k++;
    n -= k;
  }
  return n === 0 ? k : k - 1;
};

Time Complexity : O(n)

---

Below 2 approaches follow a similar pattern.

Let's assume we can form K full rows, we get a sum of K terms.
1 + 2 + 3 + 4 ... + k = Arithmetic progression , sum of K terms [k(k+1)/2]

the equation would be k(k+1) / 2 <= n

We need to find the maximum K value which satisfies the above equation.

Since our series is in incremental order of coins. We can use the binary search approach to find the maximum value of K

Binary Search Approach:

let arrangeCoins = function (n) {
  let low = 0,
    high = n;
  let k, current;

  while (low <= high) {
    k = parseInt(low + (high - low) / 2);
    current = (k * (k + 1)) / 2;
    if (current === n) {
      return k;
    }
    if (n > current) {
      low = k + 1;
    } else {
      high = k - 1;
    }
  }
  return high;
};

Time complexity : O(logn)

---

Math Approach (Efficient approach):

Lets look at our equation once again.

k(k+1) / 2 <= n

Let's solve this

k(k+1) <= 2n

Add 1/4 on both sides of the equation.
So that, left side of the equation can be formed into (a+b)^2

(k^2 + k + 1/4) <= (2n + 1/4)

(k + 1/2)^2 <= (8n+1)/4

k <= sqrt((8n+1)/4) - 1/2

Our final equation would be

k <= (sqrt(8n+1) -1)/2

Now using this formula, our code would be:

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

Time Complexity: O(logn)

---

Refer source code of other problems