1060

class Solution {
public:
    int missingElement(vector<int>& nums, int k) {
        int n = nums.size();
        // If k > last element of array.
        if(k > countMissing(nums, n-1)){
            return nums[n-1] + k - countMissing(nums, n-1);
        }

        // Binary Search the range and find lower bound where missing nums >= k.
        int l = 0, r = n-1;
        while(l < r){
            int mid = (l+r)/2;
            if(countMissing(nums, mid) < k)
                l = mid+1;
            else r = mid;
        }
        return nums[l-1] + k - countMissing(nums, l-1);
    }

    int countMissing(vector<int> &nums, int idx){
        return nums[idx] - nums[0] - idx;
    }
};