BinarySearch 0588 Kth Missing Number

Problem statement

https://binarysearch.com/problems/Kth-Missing-Number/

Solution

Variation of Leetcode 1539. Kth Missing Positive Number.

Complexity

It is O(log n) for time and O(1) for space.

Code

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