Drop Eggs

Solution

See this video in Chinese (opens new window) for perfect explanation on this problem and the following harder problem Super Egg Drop.

Math

The first egg is dropped to minimize the search area, with intervals $n, n-1, n-2, \cdots, 1$. The second egg is dropped to test the exact location. In this way, the total number of drops is a constant, x.

import math

def dropEggs(self, n):
    x = int(math.sqrt(2 * n))
    while x * (x+1) / 2 < n:
        x += 1
    return x