algorithms/leetcode/1884-EggDropWithTwoEggsAndNFloors.go at master · freewu/algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
package main

// 1884. Egg Drop With 2 Eggs and N Floors
// You are given two identical eggs and you have access to a building with n floors labeled from 1 to n.

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

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

// Return the minimum number of moves that you need to determine with certainty what the value of f is.

// Example 1:
// Input: n = 2
// Output: 2
// Explanation: 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't, we know that f = 1.
// Otherwise, if both eggs survive, we know that f = 2.

// Example 2:
// Input: n = 100
// Output: 14
// Explanation: 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.

// Constraints:
//     1 <= n <= 1000

import "fmt"

func twoEggDrop(n int) int {
    sum, res := 0,0
    for i := 1 ; sum < n ; i++ {
        sum += i
        res = i
    }
    return res
}

func twoEggDrop1(n int) int {
    sum, res := 0,0
    for sum < n {
        res++
        sum += res
    }
    return res
}

func main() {
    // Example 1:
    // Input: n = 2
    // Output: 2
    // Explanation: 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't, we know that f = 1.
    // Otherwise, if both eggs survive, we know that f = 2.
    fmt.Println(twoEggDrop(2)) // 2
    // Example 2:
    // Input: n = 100
    // Output: 14
    // Explanation: 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.
    fmt.Println(twoEggDrop(100)) // 14

    fmt.Println(twoEggDrop(1)) // 1
    fmt.Println(twoEggDrop(999)) // 45
    fmt.Println(twoEggDrop(1000)) // 45

    fmt.Println(twoEggDrop1(2)) // 2
    fmt.Println(twoEggDrop1(100)) // 14
    fmt.Println(twoEggDrop1(1)) // 1
    fmt.Println(twoEggDrop1(999)) // 45
    fmt.Println(twoEggDrop1(1000)) // 45
}