Question

Intuition

Approach

Complexity

• Time complexity: $$O(log\ n)$$

• Space complexity: $$O(1)$$

Code

class Solution:
    def arrangeCoins(self, n: int) -> int:
        lowestNumberOfRows, highestNumberOfRows = 1, n
        completeRows = 1
        while (lowestNumberOfRows <= highestNumberOfRows):
            builtRows = (lowestNumberOfRows + highestNumberOfRows) // 2
            numberOfCoins = (builtRows * (builtRows + 1)) / 2 #using the formula for sum of numbers from 1 to n
            if numberOfCoins == n:
                return builtRows
            elif numberOfCoins < n:
                completeRows = builtRows
                lowestNumberOfRows = builtRows + 1
            else:
                highestNumberOfRows = builtRows - 1
        return completeRows
        

Result