Swift Solution using binary search


  • 0
    M

    Using arithmetic progression, we get s = n*(a1+an)/2 <= input, a1 = 1, an = a1+(n-1)*d = n, we've got s = n(n+1)/2, then we use binary search to find n

    class Solution {
        func arrangeCoins(_ n: Int) -> Int {
            var l = 1
            var r = n
            while l<=r {
                let mid = l+(r-l)/2
                let s = mid*(mid+1)/2
                if s == n {
                    return mid
                } else if s>n {
                    r = mid-1
                } else {
                    l = mid+1
                }
            }
            return r
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.