-
Notifications
You must be signed in to change notification settings - Fork 21
Expand file tree
/
Copy pathmissingNumber.java
More file actions
31 lines (30 loc) · 845 Bytes
/
Copy pathmissingNumber.java
File metadata and controls
31 lines (30 loc) · 845 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/* binary search approach */
public class Solution {
public int missingNumber(int[] nums) {
if(nums == null || nums.length == 0){
return 0;
}
Arrays.sort(nums);
int left = 0, right = nums.length;
while(left < right){
int mid = (left + right) / 2;
if(nums[mid] > mid){/* here the number starts from 0, if starts from k, change to nums[mid] > mid + k, return left + k */
right = mid;
}else{
left = mid + 1;
}
}
return left;
}
}
/* o(n) solution using xor */
public class Solution {
public int missingNumber(int[] nums) {
int res = nums.length;
for(int i = 0; i < nums.length; i++){
res ^= i;
res ^= nums[i];
}
return res;
}
}