Prev | Next
Problem #16 HARD

The Fragile Floors

Google Amazon Optimization Logic

Problem Statement

You work in a testing lab with a tall building and two identical test samples. Each sample will survive any fall below a certain critical floor and shatter on any fall at or above it. You do not know the critical floor. The building has 100 floors. You can drop each sample as many times as it survives — but once a sample breaks, it is gone. What is the fewest number of drops you need to guarantee finding the exact critical floor?

Answer & Quick Explanation

Think you've got it? Click below to check your answer.

14 drops. Use gaps of 14, 13, 12, 11... (shrinking by 1). When sample #1 breaks, sample #2 scans the gap linearly. The design ensures both phases together never exceed 14 drops regardless of the critical floor.

Detailed Editorial Solution

Want to see the step-by-step breakdown? Click below to reveal the editorial.

Let the first drop happen at floor n. After each survival, reduce the gap by 1. This balances the two phases: first sample coverage plus second sample linear scan always sum to the same total. Step 1: We want the smallest n where n + (n−1) + (n−2) + ... + 1 ≥ 100. This is n(n+1)/2 ≥ 100, giving n = 14 (since 14×15/2 = 105). Step 2: Drop sample #1 from floor 14. If it breaks: check floors 1 through 13 one by one with sample #2. Worst case: 1 + 13 = 14 drops. Step 3: If sample #1 survives floor 14, next drop it from floor 27 (gap of 13). If it breaks here: check floors 15 through 26 linearly. Worst case: 2 + 12 = 14 drops. Step 4: Continue with floors 39 (gap 12), 50 (gap 11), 60 (gap 10), 69 (gap 9), 77 (gap 8), 84 (gap 7), 90 (gap 6), 95 (gap 5), 99 (gap 4), 100 (gap 1). Step 5: At each stage, the number of first-sample drops used plus the remaining gap equals exactly 14. Step 6: No matter where the critical floor sits, you never exceed 14 total drops. Key Insight: The shrinking-gap strategy keeps the worst case constant. Each drop of sample #1 'consumes' one unit of slack from sample #2's remaining scan, maintaining the invariant: drops_used + gap_remaining = 14.