""" 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()
""" 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()
""" 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()