441. Arranging Coins

[Tcdian]

441. Arranging Coins

你总共有 n 枚硬币，你需要将它们摆成一个阶梯形状，第 k 行就必须正好有 k 枚硬币。

给定一个数字 n，找出可形成完整阶梯行的总行数。

n 是一个非负整数，并且在32位有符号整型的范围内。

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.

[Tcdian]

Solution

• JavaScript Solution

/**
 * @param {number} n
 * @return {number}
 */
var arrangeCoins = function(n) {
    let left = 0;
    let right = n;
    while (left <= right) {
        const mid = (left + right) >> 1;
        const count = (1 + mid) * mid / 2;
        if (count <= n && count + mid + 1 > n) {
            return mid;
        } else if (count > n) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
};

• TypeScript Solution

function arrangeCoins(n: number): number {
    let left = 0;
    let right = n;
    while (left <= right) {
        const mid = (left + right) >> 1;
        const count = (1 + mid) * mid / 2;
        if (count <= n && count + mid + 1 > n) {
            return mid;
        } else if (count > n) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
};