Problem

You have n coins and you want to build a staircase with these coins. The staircase consists of k rows where the ith row has exactly i coins. The last row of the staircase may be incomplete.

Given the integer n, return the number of complete rows of the staircase you will build.

Examples

Example 1:

$$ \begin{matrix} \colorbox{orange} $ \\ \colorbox{orange} $ & \colorbox{orange} $ \\ \colorbox{orange} $ & \colorbox{orange} $ &\colorbox{white} 0 \end{matrix} $$

Input:
n = 5
Output:
 2
Explanation: Because the 3rd row is incomplete, we return 2.

Example 2:

$$ \begin{matrix} \colorbox{orange} $ \\ \colorbox{orange} $ & \colorbox{orange} $ \\ \colorbox{orange} $ & \colorbox{orange} $ &\colorbox{orange} $ \\ \colorbox{orange} $ & \colorbox{orange} $ & \colorbox{white} 0 & \colorbox{white} 0 \\ \end{matrix} $$

Input:
n = 8
Output:
 3
Explanation: Because the 4th row is incomplete, we return 3.

Solution

Method 1 - Greedy

  • For each row keep on subtracting the num elements in row, till n is positive and count the rows

Eg. n = 8; numCoinsInRow = 1; row = 1; n = 7 numCoinsInRow = 2; row = 2; n = 5; numCoinsInRow = 3; row = 3; n = 2 numCoinsInRow = 4, n = -2 so break; Answer = row = 3

Code

Java
public int arrangeCoins(int n) {
	int i = 1; // which row we are on
	while(n > 0){ // checking to see if we have used all our coins
		i++; // increasing our row
		n = n-i; // adding coins to our row
	}
	return i-1; // we return our current row minus one because the last row is our completed row
}

Complexity

  • ⏰ Time complexity: O(sqrt (n)) - We take larger and larger chunks with each iteration
  • 🧺 Space complexity: O(1)

Method 2 - Using Arithematic Progression and Binary Search

Each row increment is following arithematic progression with a = 1, and d = 1. When we have 3 rows, we have 6 coins. When we have 4 rows, we have 10 coins. When we have N rows, we have N(N+1) / 2 coins.

We can implement Binary Search now, by setting

  • Our “left” marker to 0
  • Our “right” marker to N, since we cannot use more coins than we our given
  • Our “pivot” to left + (right-left)/2, we use this equation instead of (left + right)/2 to avoid getting an integer overflow
  • The “area” of our proposed staircase to (pivot * (pivot+1))/2

To implement Binary Search with these variables, we:

  • Check if our area is equal to the amount of coins that we are given
    • at which point we return “pivot”
  • If we used more coins than our limit of coins, then we set “right” to “pivot-1”, to use less coins during the next iteration
  • If we used less coins than our limit of coins, then we set “left” to “pivot+1”, to use more coins during the next iteration
  • When our “left” is greater than our “right”, our “left” will be set to a incomplete row and our “right” will be set to a complete row, so we return “right”

Code

Java
public int arrangeCoins(int n) {
	long left = 0; // we use "long" because we may get an integer overflow
	long right = n;
	while(left <= right){
		long mid = left + (right - left) / 2;
		long coinsUsed = mid * (mid + 1)/2;
		if(coinsUsed == n){
			return (int)pivot;
		}
		if(n < coinsUsed){
			right = mid-1;
		}
		else{
			left = mid + 1;
		}
	}
	return (int)right; // cast as an "int" because it was initiliazed as a "long"
}

Complexity

  • ⏰ Time complexity: O(log (n))
  • 🧺 Space complexity: O(1)

Method 3 - Using Arithmetic Progression and Algebra

So, now we have to so n coins and we have to find N.

1,2,3......N = sum  
n*(n+1)/2 = sum  
n^2 + n = 2 * sum  
n^2 + n + 1/4 = 2 * sum + 1/4  
(n+1/2)^2 = 2 * sum + 1/4  
n+0.5 = (2 * sum + 1/4)^1/2  
n = -0.5 + (2 * sum + 0.25)^0.5*

Code:

public int arrangeCoinsNumerical(int n) {
	return (int) ((-1 + Math.sqrt(1 + 8 * (long) n)) / 2);
}

Complexity

  • ⏰ Time complexity: O(log n)
  • 🧺 Space complexity: O(1)