Program to find the maximum height when coins are arranged in triangle using Python

Introduction

Given N number of coins, the task is to construct a triangle of maximum height H and print the max height.

Program to find the maximum height when coins are arranged in triangle using Python

Program

def sq_root(val):
    n = val 
    m = 1
# Accuracy  
    e = 0.000001
    while (n - m > e):
        n = (n + m) / 2
        m = val/n
        
    return n 
def find(ip_num)
    val = 1 + 8*ip_num 
# Find max height and return
    maxHeight = int((-1 + sq_root(val)) / 2)
    print("The maximum height is: ",maxHeight) 
ip_num = int(input("Enter the number of coins: "))
find(ip_num)

Output

Program to find the maximum height when coins are arranged in triangle using Python Output

Explanation

Approach:

  • Relation between number of coins N and height H : H2 + H – 2*N <= 0 (ignoring negative root). Therefore, the maximum height H obtained by formula: (-1 + √(1+8N) )/2.
  • To solve √(1+8N), we have used Babylonian method (used in function sq_root).

Leave a comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.