Drop Eggs

https://www.lintcode.com/problem/drop-eggs

See this video for perfect explanation on this problem and the next harder problem.

# Solution

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

import math
class Solution:
    """
    @param n: An integer
    @return: An integer
    """
    def dropEggs(self, n):
        x = int(math.sqrt(2 * n))
        while x*(x+1)/2 < n:
            x += 1
        return x
Last Updated: 9/21/2020, 4:44:16 PM