Problem statement

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

Solution

Very similar to problem 1539. Kth Missing Positive Number, but here we need to shift k to k + arr[0] - 1, because we need to start with arr[0] and not 0.

Complexity

Time complexity is O(log n), space complexity is O(1) if we do not count input data.

Code

class Solution:
    def missingElement(self, arr, k):
        beg, end = 0, len(arr)
        while beg < end:
            mid = (beg + end) // 2
            if arr[mid] - mid < k + arr[0]:
                beg = mid + 1
            else:
                end = mid
        return end + k + arr[0] - 1