Abstract / Summary

Find the minimum number of drops needed to determine the highest floor an egg can be dropped from with 2 eggs and n floors.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 75% (80k+ submissions).

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a single class Solution with a method twoEggDrop that computes the minimum number of moves required to determine the highest safe floor in the classic two-egg drop problem for a building with n floors. The algorithm relies on a closed-form mathematical expression rather than iterative or recursive search, delivering an immediate answer for any non-negative integer n.

Core Logic

The heart of the method consists of three operations performed in a single expression:

return int(sqrt(2 * n) + 0.5)

First, the product 2 * n scales the floor count to match the triangular number relationship underlying the optimal strategy. Next, sqrt extracts the square root of that product, yielding a real number that approximates the required number of drops. Adding 0.5 implements a rounding-to-nearest-integer step, and finally int truncates the fractional part, delivering the integer result expected by the problem statement.

Edge Cases Handled

When n equals zero, the multiplication yields zero, the square root is zero, and after adding 0.5 the conversion to int returns zero. This correctly indicates that no drops are needed in a building with no floors. For n equal to one, the calculation proceeds as sqrt(2) ≈ 1.414, the addition of 0.5 produces approximately 1.914, and truncation yields 1, which matches the intuitive answer that a single drop suffices for a single floor. The formula also gracefully handles very large values of n because the square-root operation scales logarithmically with the magnitude of the input, avoiding overflow or excessive computation time.

Performance Optimizations

The method achieves optimal performance by avoiding any form of iteration, recursion, or dynamic programming. By directly applying the mathematical relationship derived from the sum of the first k natural numbers (k(k+1)/2 ≥ n), the implementation reduces the problem to a constant-time arithmetic evaluation. The use of the built-in sqrt function leverages highly optimized native code, and the rounding technique (+ 0.5 followed by int) eliminates the need for explicit rounding functions, further minimizing overhead.

Mathematical Basis

The expression corresponds to the smallest integer k such that the triangular number k(k+1)/2 meets or exceeds n. Solving the quadratic inequality k^2 + k - 2n ≥ 0 yields the positive root (-1 + sqrt(1 + 8n)) / 2. Simplifying this root and applying a rounding adjustment leads to the compact form int(sqrt(2 * n) + 0.5). This derivation ensures that the returned value is the minimal number of moves required under the optimal two-egg strategy.

Imagine you have a tall building with many different floors and a couple of eggs. The goal is to find out exactly how high you can drop an egg from without it breaking. Because you only have two eggs, you have to be very careful. If you drop the first egg from a floor and it breaks, you only have one egg left, so you have to test every single floor below it one by one to see when it would have been safe. This code is a clever shortcut to figure out the fewest number of tries you need to be absolutely sure about the result. It uses a mathematical pattern to calculate the best skipping distance. By jumping up the building in smaller and smaller steps, you make sure you never run out of eggs before finding the answer. It is like balancing a puzzle where you trade off taking big jumps against making sure you do not lose your tools.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: constant
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++			Python	Java		TS
	WalkCCC	C++				Java
	leetcode.ca	C++			Python	Java	Go	TS
	Progiez	C++			Python	Java
github	black-shadows	C++
	charles-wangkai					Java
	everthis		JS
	fsq	C++
	haoel	C++
	JoshCrozier		JS
	lkwq007				Python
	shreymehul			C#
	suxrobGM			C#
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
haoel	C++
JoshCrozier	JavaScript
lkwq007	Python
shreymehul	C#
suxrobGM	C#
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality