Solution 1 - Iterative Subtraction

Given n coins, build a staircase where the ith row has exactly i coins. The last row may be incomplete. Return the number of complete rows. We subtract row counts one at a time until we can't fill the next row.

TimeComplexity: O(\sqrt{n})

SpaceComplexity: O(1)

""" 0441.1 - Arranging Coins - Solution 1 - Iterative Subtraction """

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def arrangeCoins(self, n: int) -> int:
        """Arranging Coins Function"""
        row = 0
        while n > row:
            row += 1
            n -= row
        return row


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().arrangeCoins(5))   # Expected: 2
    print(Solution().arrangeCoins(8))   # Expected: 3
    print(Solution().arrangeCoins(1))   # Expected: 1
    print(Solution().arrangeCoins(0))   # Expected: 0


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

Solution 2 - Binary Search

The total coins needed for k complete rows is k * (k + 1) / 2. We binary search for the largest k where this sum is ≤ n.

TimeComplexity: O(\log n)

SpaceComplexity: O(1)

""" 0441.2 - Arranging Coins - Solution 2 - Binary Search """

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def arrangeCoins(self, n: int) -> int:
        """Arranging Coins Function"""
        left, right = 0, n
        while left <= right:
            mid = (left + right) // 2
            coins_needed = mid * (mid + 1) // 2
            if coins_needed == n:
                return mid
            elif coins_needed < n:
                left = mid + 1
            else:
                right = mid - 1
        return right


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().arrangeCoins(5))   # Expected: 2
    print(Solution().arrangeCoins(8))   # Expected: 3
    print(Solution().arrangeCoins(1))   # Expected: 1
    print(Solution().arrangeCoins(0))   # Expected: 0


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

Solution 3 - Math (Quadratic Formula)

Using the formula k * (k + 1) / 2 ≤ n, we solve the quadratic equation k² + k - 2n = 0 directly. The positive root gives us the answer: k = (-1 + √(1 + 8n)) / 2. We take the floor of this value.

TimeComplexity: O(1)

SpaceComplexity: O(1)

""" 0441.3 - Arranging Coins - Solution 3 - Math (Quadratic Formula) """

#####################################################################################
# Imports
#####################################################################################
import math

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def arrangeCoins(self, n: int) -> int:
        """Arranging Coins Function"""
        return int((-1 + math.sqrt(1 + 8 * n)) / 2)


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().arrangeCoins(5))   # Expected: 2
    print(Solution().arrangeCoins(8))   # Expected: 3
    print(Solution().arrangeCoins(1))   # Expected: 1
    print(Solution().arrangeCoins(0))   # Expected: 0


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

0441 - Arranging Coins

Solution 1 - Iterative Subtraction

Solution 2 - Binary Search

Solution 3 - Math (Quadratic Formula)