Earliest Faulty Version

In this problem, you are given a number n which represents the total number of versions and an unknown first faulty version. All versions from the first faulty version onward are faulty.

Your task is to find the earliest faulty version using an efficient algorithm (binary search). The binary search solution should minimize the number of calls to the faulty-check function.

Formally, let the versions be numbered from 1 to n. There exists an integer f (1 ≤ f ≤ n) such that version f and every version subsequent to f are faulty, while all versions before f are not faulty. You need to determine the value of f.

The function isFaulty(version) is defined such that it returns true if the version is faulty and false otherwise. Use this function to implement your solution.

inputFormat

The input consists of two integers separated by spaces or newlines:

• n: the total number of versions.
• f: the first version which is faulty.

You may assume that 1 ≤ f ≤ n. Versions from f to n are faulty and versions before f are not faulty.

outputFormat

Output a single integer which is the earliest faulty version, i.e. the value of f.

5
3

3