Lc1539

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
    """
    some restrains:
    1. sorted(strickly increasing) array, ideally always start with 1 
    2. 
    """
    # time O(N) space O(1)
        n = len(arr)
        if arr[0] != 1:
            if  k -(arr[0]-1) <= 0:
                    return k
            else:
                k = k - (arr[0]-1)
        for r in range(1,n): 
            if arr[r]-arr[r-1] > 1:
                diff = arr[r]-arr[r-1]-1
                if k-diff <= 0 :
                    return arr[r-1]+k
                else:
                    k -= diff
        return arr[-1] + k

"""
assuming first m elements are not missing.  for (m+1) th, the number of missing elements are A[m] - m - 1 
we need to find a point where kth number is between (A[m],A[m+1]]
"""
# time O(lgN) space O(1)
class Solution:
    def findKthPositive(self, A: List[int], k: int) -> int:
        l,r = 0, len(A)
        while l < r:
            mid = l + (r-l)//2 
           # print(f'l is {l}, r is {r}, mid is {mid}, m val is {A[mid]}')
            if A[mid] - mid -1 < k :
                l = mid + 1
            elif A[mid] - mid -1 == k:
                r = mid 
                #return mid-1+k 
            elif A[mid] - mid -1 > k:   
                r = mid  
        return l+k