Find the Earliest Failing Version

# Find the Earliest Failing Version Versions are numbered from `1` through `n`. There is a first failing version: every earlier version passes, and that version and every later version fail. Implement `Solution.firstBadVersion(n)` to return the smallest failing version number. Use the provided `isBadVersion(version)` API to inspect a version, and minimize the number of API calls. The latest version is guaranteed to fail. ### Interface `isBadVersion(version)` returns a Boolean: `True` for a failing version and `False` for a passing one. Query only version numbers in `1..n`. For this Python practice interface, construct `Solution(isBadVersion)` with the supplied callable, then call `firstBadVersion(n)`. The constructor injects the API; it does not reveal its hidden boundary. The candidate must not inspect the callable's owner, attributes, closure or source. The first failing version shown in an example is private setup data, not a parameter to `firstBadVersion`. ### Examples **Example 1:** There are `12` versions, and the private test service's first failing version is `9`. Calling `firstBadVersion(12)` returns `9`: versions `1..8` pass and `9..12` fail. **Example 2:** There are `7` versions, and every version fails. Calling `firstBadVersion(7)` returns `1`. ### Constraints - `1 <= first failing version <= n <= 2**31 - 1`. - API answers are consistent throughout the call and have the stated monotone ordering. - The task asks you to minimize calls; it does not prescribe a numeric call cap. ### What a Strong Answer Covers - Return the first failing version, rather than just any failing version. - Handle a single version and failures beginning at either endpoint. - Account for API calls and keep every query within the valid range. ### Follow-up Questions - What contract change would be needed if all versions were allowed to pass? - How would you test correctness and API usage without exposing hidden data to the candidate?