Last Updated: 2024-03-10 01:56:44 Sunday

-- TOC --



class Solution:
    def twoEggDrop(self, n: int) -> int:
        sub = [[0]*(n+1) for _ in range(2+1)]
        d = 0
        while sub[2][d] < n:
            d += 1
            for k in range(1,2+1):
                sub[k][d] = sub[k-1][d-1] + sub[k][d-1] + 1
        return d


import math

class Solution:
    def twoEggDrop(self, n: int) -> int:
        return math.ceil(math.sqrt(0.25+n*2)-0.5)


Given 2 eggs and a building of N floors, we need to figure out the time complexity of the best strategy that could determine the lowest egg-broken-floor. Best strategy means to achieve this goal with minimum drop number in worst case. Fortunately, there are only 2 eggs! We have an even-split-strategy with time complexity of \(O(2\sqrt N)\) in class. But the best strategy is uneven with time complexity of \(O(\sqrt{2N})\). Now, let’s proof it.


Let \(T(N,2)\) represents the drop number with 2 eggs and a building of N floors. This function is always increasing since the higher building the more drop number. Furthermore, after we let the first egg go in \(kth\) floor, there are only 2 choices left. If the first egg broken, we have to use the last egg to test floor bottom-up from 1 to k-1 floor. Then the drop number is just k-1. If not broken, we still have 2 eggs to test the upper part of the building which is from k+1 to N floor. If the first egg is not broken, the question is reduced to \(T(N-k,2)\). We still have 2 eggs but are facing a lower building technically.

How to choose the k? The worst case minimum drop number comes with \(k-1=T(N-k,2)\). In another word, only when the drop number given the first egg broken equals the drop number given it not broken, we get the best egg-dropping strategy, which has minimum drop number with certainty. It’s the best strategy at worst case.

Suppose there are total n drops needed, and there is a distinct k in each drop, which we use \(k_i(1\le i\le n)\) to represent. Here we have:





Since \(T(0,2)=0\),



If the first egg broken at the 1st drop, we have to test k_1-1 floor bottom-up one by one, so,


If the first egg broken at the 2nd drop, we have to test k_2-1 floor bottom-up one by one, so,


and so on,




Wrap all these up,




Solve this quadratic function, we get:


Get rid of the meaningless negative solution, we get the n and the final big-oh:

$$n=\frac{\sqrt{1+8N\ }-1}{2}=\sqrt{\frac{1}{4}+2N}-\frac{1}{2}=O\left(\sqrt{2N}\right)$$

So, the best strategy of \(T(N,2)\) in worst case has time complexity \(O(\sqrt{2N})\).



-- EOF --

-- MORE --