class Solution {
public int missingElement(int[] nums, int k) {
int[] cnts = new int[nums.length];
missingCount(nums, cnts);
int lo = 0;
int hi = nums.length - 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
int cnt =cnts[mid];
if (cnt < k) {
lo = mid + 1;
} else {
hi = mid;
}
}
int cnt = cnts[lo];
int num = nums[lo] - 1;
if (cnt < k) {
return nums[nums.length - 1] + (k - cnt);
}
while (cnt > k) {
cnt--;
num--;
}
return num;
}
private void missingCount(int[] nums, int[]cnts) {
int cnt = 0;
for (int i = 1; i < nums.length; i++) {
cnt += nums[i] - nums[i - 1] - 1;
cnts[i] = cnt;
}
}
}