441. Arranging Coins

441. Arranging Coins

題意

給你 n 個硬幣，建造一個階梯，這個階梯第 i 列就會是 i 個硬幣

• 最後一行有可能未完成

回答 n個硬幣可以建立幾階

限制

• 1 <= n <= 2^31 - 1

思考

• 可以透過從 1 開始不斷往上加，直到超過 n

  • 時間複雜度為 O(N)

• 由題目可以歸納出題意為計算 1 + 2 + … + (i - 1) <= n < 1 + 2 + … + i

  • 由 1 加到 i 的計算方法為 i * (i + 1) / 2

  • 由限制 n <= 2^31 - 1

    • 可以簡略計算 2^32 <= (i^2 + i) / 2

    • $2^{32}=(2^{16})^{2}=65536^2$

    • 可知 i 的範圍會介於 1~65536之間

  • 在 i = 1~65536 之間找到 $\dfrac{(i - 1) * i}{2} \le n < \dfrac{(i + 1) * i}{2}$，可以使用binary search

Solution

#define UPPER_BOUND 65536
#define SUM(x) (((long)x + 1) * x / 2)

class Solution {
public:
    int arrangeCoins(int n) {
        // i * (i - 1) / 2 < n <= (1 + i) * i / 2
        int i = 1;
        int j = UPPER_BOUND;
        while (i <= j) {
            int mid = i + (j - i) / 2;
            long sum = SUM(mid);
            if (sum == n) {
                return mid;
            }

            if (sum > n) {
                j = mid - 1;
            } else {
                i = mid + 1;
            }
        }

        return j;
    }
};

Time Complexity: O(1)，since $\log_{2}{65536}=16$

Space Complexity: O(1)