tags: 441. Arranging Coins

441. Arranging Coins

• 題目

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.

#Example 1:

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

Example 2:

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

Constraints:

​​​​1 <= n <= 231 - 1

---

• 解法

不跑迴圈方式計算，直接找出row的關係(簡寫r)

1+2+3+…
可以透過梯形公式計算

r(r+1)/2 ≤ n

整理過後

r^2 + 1r ≤ 2n

希望得到的結果是r = xxxx
透過(r+b)^2跟n的關係, 再開根號
就可以知道算出r跟n的關係

---

國中數學的 (a+b)^2 公式, 觀察一下

(a+b)^2 = a^2+2ab+b^2 
        ||
(r+b)^2 = r^2+2rb+b^2
          r^2+r+ ...  <=希望整理的樣子

其中，b是數字,公式後會產生額外的數字,再扣掉就好

先從2rb=r整理, 所以2b=1, 故b=1/2

會跟原本的函式多1/4(帶回原式時需扣掉)

(r+1/2)^2 = r^2+ 2*r*1/2b + (1/2)^2 = r^2 + r + 1/4

調整原本函式

r^2 + 1r ≤ 2n

(r^2 + 1r + 1/4) - 1/4 ≤ 2n

(r+1/2)^2 - 1/4 ≤ 2n

(r+1/2)^2 ≤ 2n + 1/4

r+1/2 ≤ sqrt(2n + 1/4)

r ≤ sqrt(2n + 1/4) - 1/2

取得 r跟n的關係 r ≤ sqrt(2n + 1/4) - 1/2

---

• Solution

class Solution {
    func arrangeCoins(_ n: Int) -> Int {
        return Int(sqrt(2.0 * Double(n) + 0.25) - 0.5)
    }
}

---

• 解法2

利用Binary Search的方式夾出答案

根據題目可以得知，最少可能1層，最多不會超過n層

1(左邊) ≤ n ≤ x(右邊, x= n, 嚴格來說 x(x+1)/ 2 >= n, 但時間上不會差太多)

每次取中間抓層數，計算那層有多少

let layer = (left + right) / 2
let midTotal = mid * (mid+1) / 2

若太多把上限往中間拉，太少把下限往右邊拉
如果剛剛好表示剛好塞滿直接結束

---

• Solution 2

class Solution {
    func arrangeCoins(_ n: Int) -> Int {        
        var left = 1, right = n // layer
        
        while left <= right {
            let mid = (left + right) / 2
            let total = (mid + 1) * mid / 2
            if total == n {
                return mid
            } else if total < n {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
        return left - 1 // not full, return last layer
    }
}