First Bad Version

Binary Search
Binary Search On Answer

You are a product manager leading a team developing a new product. Versions [1..n] are all derived from version 1, and once a version is bad, every version after it is also bad. You are given an API isBadVersion(v) that returns whether version v is bad. Return the first bad version using as few API calls as possible.

The answer space is monotone — false, false, ..., false, true, ..., true — so this is a textbook binary search on the answer space with O(log n) calls.

Examples

Example 1

Input

n

1

2

3

4

5

firstBad4

Output

4

Example 2

Input

n

1

firstBad1

Output

1

Constraints

1 ≤ n ≤ 2³¹ − 1
At least one version is bad, so the answer is between 1 and n.

Stuck? Hint 1

Maintain the invariant: every version ≤ lo is known good, every version ≥ hi is known bad.

Input

1

2

3

4

5

firstBad4

Expected Output

Ctrl / ⌘ + Enter

First Bad Version

Binary Search
Binary Search On Answer

You are a product manager leading a team developing a new product. Versions [1..n] are all derived from version 1, and once a version is bad, every version after it is also bad. You are given an API isBadVersion(v) that returns whether version v is bad. Return the first bad version using as few API calls as possible.

The answer space is monotone — false, false, ..., false, true, ..., true — so this is a textbook binary search on the answer space with O(log n) calls.

Examples

Example 1

Input

n

1

2

3

4

5

firstBad4

Output

4

Example 2

Input

n

1

firstBad1

Output

1

Constraints

1 ≤ n ≤ 2³¹ − 1
At least one version is bad, so the answer is between 1 and n.

Stuck? Hint 1

Maintain the invariant: every version ≤ lo is known good, every version ≥ hi is known bad.

Input

1

2

3

4

5

firstBad4

Expected Output

Ctrl / ⌘ + Enter