Two Billion Plus One

You are binary searching on the answer. The answer can be as large as $2 \cdot 10^9$ , so you write:

int lo = 1, hi = 2000000000;
while (lo < hi) {
  int mid = (lo + hi) / 2;
  if (feasible(mid)) hi = mid;
  else lo = mid + 1;
}

feasible is correct and hi fits in an int ( $2^{31} - 1 = 2147483647$ ). Where does this break?

Write int mid = (lo + hi) >> 1;. Shifting avoids the division and therefore avoids the overflow.

lo + hi overflows as soon as lo exceeds about $1.47 \cdot 10^{8}$ , since $2147483647 - 2 \cdot 10^{9} = 147483647$ . Compute lo + (hi - lo) / 2 instead.

It does not break. Both lo and hi are valid int values at every step, and mid always lies between them.

It breaks only when the true answer is close to hi, so widening hi to 4000000000 and using long long for hi alone is enough.