https://leetcode.com/problems/arranging-coins/

arrangingCoins.js

/*
Idea: Count up the steps we can make one by one.
- O(n) I think...
*/
var arrangeCoins = function(n) {
    let rows = 0;
    let prevRowSize = 0;
    
    while(n > 0){
        if(n >= ++prevRowSize) rows++;
        n -= prevRowSize;
    }
    
    return rows;
};

/*
Second Idea: since the steps are of size 1, 2, 3...
we *should* be able to tell how many coins are required
for the ith step with some sort of forumla.
- We know that two nested for-loops over a string of
  length n runs in O(n**2 / 2). There's probably some 
  constant in there. Let's write down a few examples and
  look for a pattern.
- 0 steps: 0
  1 steps: 1
  2 steps: 3
  3 steps: 6 ... so 3*something / 2 = 6...
  4 steps: 10 .. so 4*something / 2 = 10..
  It looks like 'something' is always i + 1!
- So our formula for how many coins are required to build
  i steps is i*(i+1) / 2
- So we can test whether we can build i steps with n coins 
  in O(1) (with this formula).
  We also know the answer is no less than 0, and definitely
  no more than n. Binary search!
- O(log(n))
*/
var arrangeCoins = function(n) {
    
    if(!n) return 0;
    
    let [l, r, result] = [1, n, 1];
    
    while(l <= r){
        const mid = Math.floor((l+r)/2);
        const required = (mid * (mid+1)) / 2;
        
        if(n >= required){
            l = mid+1;
            result = Math.max(result, mid);
        }else{
            r = mid-1;
        }
    }
    
    return result;
};

/*
Idea: Wait... we have a formula. Can't we just
solve it? Yes! Here's the algebra, where n is
the number of coins and k is the number of steps.
n >= k * (k+1) / 2         // this is the formula we came up with earlier
2n >= k * (k+1)
2n >= k^2 + k

// This is a quadratic equation in the form ax**2 + bx + c.
// In this case, a=1, b=1 and c=0
// see https://en.wikipedia.org/wiki/Completing_the_square for how to
// factorise this into the next line

2n >= (k - 0.5, 2)^2 + 1/4 
2n + 1/4 >= k + 0.5
Math.sqrt(2n + 1/4) >= k - 0.5
Math.sqrt(2n + 1/4) - 0.5 >= k

// So to solve it, set k = that monstrosity and round it down!
return Math.floor(Math.sqrt(2 * n + 0.25) - 0.5);

// O(1)
*/
var arrangeCoins = function(n) {
  return Math.floor(Math.sqrt(2 * n + 0.25) - 0.5);
};