題目:

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.

給定金幣的數量,開始排列,第一行排一個,第二行排兩個,第三行排三個......
判斷總共能排出完整的幾行金幣

這題我用二分搜來做

class Solution:
    def arrangeCoins(self, n: int) -> int:
        if n==1: #防止n為1
            return 1
        
        l=0
        r=n
        while l+1!=r:
            mid=(l+r)//2
            x=((1+mid)*mid)//2
            if x==n:
                return mid
            
            if x<n:
                l=mid
            elif x>n:
                r=mid
        
        return l

我們知道1+2+3+.....+n的公式為( (1+n) * n )//2

設好左右邊界(l=0,r=n),mid設為(l+r)//2
若((1+mid) * mid)//2等於n
表示該金幣數可以剛好排mid行,所以直接回傳mid
而((1+mid) * mid)//2 大於n則r下降至mid,反之l上升至mid
直到l,r相鄰
表示該金幣數可以排l餘行,所以回傳l
最後執行時間39ms(faster than 91.95%)

那我們下題見