Leetcode 1059 Solution

This article provides solution to leetcode question 1059 (missing-element-in-sorted-array)

https://leetcode.com/problems/missing-element-in-sorted-array

Solution

class Solution { public: int missingElement(vector<int>& nums, int k) { vector<int> a; a.push_back(0);
int last_gap = 0;
for (int i = 0; i < nums.size() - 1; i++) { int curr_gap = nums[i + 1] - nums[i] - 1; a.push_back(curr_gap + a[a.size() - 1]); }
int l = 0; int r = a.size() - 1; k++;
while (l < r) { int m = (l + r) / 2; if (a[m] >= k) r = m; else l = m + 1; }
if (a[l] < k) l++;
return nums[l - 1] + k - a[l - 1]; } };