The below is two solutions for Leet code 374
Solution one
public class Solution extends GuessGame {
public int guessNumber(int n) {
int high = n;
int low = 1;
while (low<=high) {
int mid = (low+high)/2;
if (guess(mid) == 0) {
return mid;
}
if (guess(mid) >0) {
low = mid +1;
} else {
high = mid -1;
}
}
return 0;
}
}
Solution two
public class Solution extends GuessGame {
public int guessNumber(int n) {
int high = n;
int low = 1;
while (low<=high) {
int mid = low + (high-low)/2;
if (guess(mid) == 0) {
return mid;
}
if (guess(mid) >0) {
low = mid +1;
} else {
high = mid -1;
}
}
return 0;
}
}
These two solutions are almost identical. However, the first solution will not pass all tests. So, what is going on? The only difference is how to calculate mid value.
//solution one
int mid = (low+high)/2;
//solution two
int mid = low + (high-low)/2;
For solution one, it will cause integer overflow for large inputs.
No comments:
Post a Comment