Robert Eisele
Engineer, Systems Architect and DBA

Hackerrank: Minimum Height Triangle

Original Problem

Given integers \(b\) and \(a\), find the smallest integer \(h\) such that there exists a triangle of height \(h\), base \(b\) , having an area of at least \(a\) .

image

Input Format

In the first and only line, there are two space-separated integers \(b\) and \(a\), denoting respectively the base of a triangle and the desired minimum area.

Constraints

  • \(1\leq b\leq 10^6\)
  • \(1\leq a\leq 10^6\)

Output Format

In a single line, print a single integer \(h\) , denoting the minimum height of a triangle with base \(b\) and area at least \(a\) .

Sample Input 0

2 2

Sample Output 0

2

Explanation 0

The task is to find the smallest integer height of the triangle with base \(2\) and area at least \(2\) . It turns out, that there are triangles with height \(2\) , base \(2\) and area \(2\) , for example a triangle with corners in the following points: \((1,1),(3,1), (1,3)\) :

image

It can be proved that there is no triangle with integer height smaller than \(2\) , base \(2\) and area at least \(2\) .

Sample Input 1

17 100

Sample Output 1

12

Explanation 1

The task is to find the smallest integer height of the triangle with base \(17\) and area at least \(100\) . It turns out, that there are triangles with height \(12\), base \(17\) and area \(102\), for example a triangle with corners in the following points: \((2,2), (19,2), (16,14)\) .

image

It can be proved that there is no triangle with integer height smaller than \(12\) , base \(17\) and area at least \(100\) .

Solution

The area of the triangle can be determined as \(a = \frac{1}{2} bh\) from which follows that the height can be calculated as \(h = \frac{2a}{b}\). Since we are looking for an integer solution with \(\geq a\), we can ceil the calculation and can implement the solution in Ruby:

def lowestTriangle(base, area)
  (2 * area / base).ceil
end

base, area = gets.split.map(&:to_f)
p lowestTriangle(base, area)

« Back to problem overview

All images are copyright to Hackerrank