0441 - Arranging Coins (Easy)

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

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

class Solution {
public:
    int arrangeCoins(int n) {
        // Gauss' formula
        // k * (k + 1) / 2 <= n
        // k * (k + 1 / 2) ^ 2 - 1 / 4 <= n
        // k = sqrt(2 * n + 1 / 4) - 1 / 2
        return sqrt(2 *(long long) n + 0.25) - 0.5;
    }
};

class Solution {
public:
    int arrangeCoins(int n) {
        // init possible range
        long long l = 1, r = n;
        while (l < r) {
            // get the middle one
            // for even number of elements, take the upper one
            long long m = l + (r - l + 1) / 2;
            // for m rows, how many coins can be put?
            long long total = m * (m + 1) / 2;
            // exclude m
            if (n < total) r = m - 1;
            // include m
            else l = m;
        }
        return l;
    }
};

class Solution:
    def arrangeCoins(self, n: int) -> int:
        left = 1
        right = n
        while left <= right:
            mid = (left + right) // 2
            temp = int(mid * (mid + 1) / 2)
            if temp == n:
                return mid
            elif temp < n:
                left = mid + 1
            else:
                right = mid - 1
        return right

/**
 * @param {number} n
 * @return {number}
 */
var arrangeCoins = function (n) {
  let left = 1;
  let right = n;
  while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    let temp = Number((mid * (mid + 1)) / 2);
    if (temp == n) {
      return mid;
    } else if (temp < n) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return right;
};