Solutions

1. Brute Force

class Solution:
    def arrangeCoins(self, n: int) -> int:
        row = 0
        while n - row > 0:
            row += 1
            n -= row
        return row

Time & Space Complexity

Time complexity: $O(\sqrt {n})$
Space complexity: $O(1)$

2. Binary Search

class Solution:
    def arrangeCoins(self, n: int) -> int:
        l, r = 1, n
        res = 0

        while l <= r:
            mid = (l + r) // 2
            coins = (mid * (mid + 1)) // 2
            if coins > n:
                r = mid - 1
            else:
                l = mid + 1
                res = max(res, mid)

        return res

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(1)$

3. Binary Search (Optimal)

class Solution:
    def arrangeCoins(self, n: int) -> int:
        if n <= 3:
            return n if n == 1 else n - 1

        l, r = 1, (n // 2) + 1
        while l < r:
            mid = (l + r) // 2
            if (mid * (mid + 1)) // 2 <= n:
                l = mid + 1
            else:
                r = mid

        return l - 1

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(1)$

4. Bit Manipulation

class Solution:
    def arrangeCoins(self, n: int) -> int:
        mask = 1 << 15
        rows = 0
        while mask > 0:
            rows |= mask
            coins = rows * (rows + 1) // 2
            if coins > n:
                rows ^= mask
            mask >>= 1
        return rows

Time & Space Complexity

Time complexity: $O(1)$ since we iterate $15$ times.
Space complexity: $O(1)$

5. Math

class Solution:
    def arrangeCoins(self, n: int) -> int:
        return int(sqrt(2 * n + 0.25) - 0.5)

Time & Space Complexity

Time complexity: $O(1)$ or $O(\sqrt {n})$ depending on the language.
Space complexity: $O(1)$