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.