<p>You are given <strong>two identical</strong> eggs and you have access to a building with <code>n</code> floors labeled from <code>1</code> to <code>n</code>.</p>

<p>You know that there exists a floor <code>f</code> where <code>0 &lt;= f &lt;= n</code> such that any egg dropped at a floor <strong>higher</strong> than <code>f</code> will <strong>break</strong>, and any egg dropped <strong>at or below</strong> floor <code>f</code> will <strong>not break</strong>.</p>

<p>In each move, you may take an <strong>unbroken</strong> egg and drop it from any floor <code>x</code> (where <code>1 &lt;= x &lt;= n</code>). If the egg breaks, you can no longer use it. However, if the egg does not break, you may <strong>reuse</strong> it in future moves.</p>

<p>Return <em>the <strong>minimum number of moves</strong> that you need to determine <strong>with certainty</strong> what the value of </em><code>f</code> is.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 2
<strong>Output:</strong> 2
<strong>Explanation:</strong> We can drop the first egg from floor 1 and the second egg from floor 2.
If the first egg breaks, we know that f = 0.
If the second egg breaks but the first egg didn&#39;t, we know that f = 1.
Otherwise, if both eggs survive, we know that f = 2.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 100
<strong>Output:</strong> 14
<strong>Explanation:</strong> One optimal strategy is:
- Drop the 1st egg at floor 9. If it breaks, we know f is between 0 and 8. Drop the 2nd egg starting from floor 1 and going up one at a time to find f within 8 more drops. Total drops is 1 + 8 = 9.
- If the 1st egg does not break, drop the 1st egg again at floor 22. If it breaks, we know f is between 9 and 21. Drop the 2nd egg starting from floor 10 and going up one at a time to find f within 12 more drops. Total drops is 2 + 12 = 14.
- If the 1st egg does not break again, follow a similar process dropping the 1st egg from floors 34, 45, 55, 64, 72, 79, 85, 90, 94, 97, 99, and 100.
Regardless of the outcome, it takes at most 14 drops to determine f.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 1000</code></li>
</ul>

class Solution:
    # what is the range of values n can take on? [1, 1000]
    # we are returning a minimized integer!
    # is the answer unique? yes
    # is the answer >= 0? yes

    # idea 0
    # binary search
    # choose halway point always?

    # idea 1
    # tabulated dynamic programming for minimization problem
    # use 2d array of size n x 2
    #   0 => first egg does NOT break
    #   1 => first egg does break
    # mix in binary search
    # example 1
    # 1
    # break? f = 0
    # not break? f = 2
    # objective fun = dp(i,break) = min number of moves
    #      needed after dropping first egg on floor i and
    #      getting result break
    # pseudocode
    # dp = [[0,0] for _ in range(n+1)]
    # dp[0] = [1,1]
    # for i in range(1,n+1):
    #    # assume dropping first egg on floor i causes a break
    #    #    so we must drop second egg on floors [0, i-1]
    #    dp[i][1] = 1+min([_,res for _,res in dp[:i]])
    #    # assume dropping first egg on floor i causes NO break
    #    #    so we must drop first egg on floors [i+1, n]
    #    dp[i][0] = 1
    # return min(dp[n])

    # idea 2
    # same as idea 1 but with top down memoized DP
    # example 1
    # 50
    # break? go to 25

    def twoEggDrop(self, n: int) -> int:
        # implement idea 1 (bottom up tabulated DP) <<< close but no cigar
        # dp = [[0,0] for _ in range(n+1)]
        # dp[0] = [1,1]
        # for i in range(1,n+1):
        #    # assume dropping first egg on floor i causes a break
        #    #    so we must drop second egg on floors [0, i-1]
        #    dp[i][1] = 1+min([ res for _,res in dp[:i] ])
        #    # assume dropping first egg on floor i causes NO break
        #    #    so we must drop first egg on floors [i+1, n]
        #    dp[i][0] = 1
        # return min(dp[n])
        # 100
        # 50 break
        # 25
        # 75

        # idea 2 (top down memoized DP) <<< close but no cigar
        # dp_cache = {}
        # def dp(currFloor, firstDown):
        #     if (currFloor, firstDown) in dp_cache:
        #         return dp_cache[(currFloor, firstDown)]
        #     if currFloor == 0:
        #         return firstDown
        #     res = float("inf")
        #     # assume breaks
        #     breaks = 1+dp(currFloor//2,True)
        #     noBreak = float("inf")
        #     if currFloor < n:
        #         # assume does NOT break
        #         noBreak = 1+dp(currFloor*0.75,False)
        #     res = min(breaks,noBreak)
        #     dp_cache[(currFloor,firstDown)] = res
        #     return res
        # return dp(n,False)

        # Fellow LeetCodian solution #1 (quadratic formula)
        #    from https://leetcode.com/problems/egg-drop-with-2-eggs-and-n-floors/solutions/5421872/here-is-an-o-1-solution-using-math-take-a-look-at-you-don-t-believe-how-easy-it-is
        # TRICK: find maximum number x such that n = x + (x-1) + (x-2) + ... + 1 + 0 = [x^2 + x] / 2
        #    => 2n = x^2 + x
        #    => 0 = [x^2 + x] - [2n]
        #    ^^^ to find the maximized value of x that minimizes
        #       the difference between the two quantities
        #       in the square brackets, we must
        #       use the quadratic formula to find the zeroes
        #       of the above equation. Using the derivative won't
        #       help here (pretty sure)

        # QUADRATIC FORMULA REVIEW
        # x^2 + x - 2n = 0 -- >  = [-b +- srt(b^2-4ac)]/2 
        # [-1 +(sqr1+4*c)]/2 
        ans = ((1+8*n)**0.5 - 1) / 2
        return math.ceil(ans)
        # Time = O(1)
        # Memory = O(1)
41