Given an array arr of positive integers sorted in a strictly increasing order, and an integer k.
Find the kth positive integer that is missing from this array.
 
Example 1:
Input: arr = [2,3,4,7,11], k = 5
Output: 9
Explanation: The missing positive integers are [1,5,6,8,9,10,12,13,...]. The 5th missing positive integer is 9.

Example 2:
Input: arr = [1,2,3,4], k = 2
Output: 6
Explanation: The missing positive integers are [5,6,7,...]. The 2nd missing positive integer is 6.

 
Constraints:

1 <= arr.length <= 1000
1 <= arr[i] <= 1000
1 <= k <= 1000
arr[i] < arr[j] for 1 <= i < j <= arr.length

Difficulty: introductory

Starter code:

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        

Solutions:
class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        lo, hi = 0, len(arr) - 1
        while lo < hi:
            mid = hi - (hi - lo) // 2
            # mid = lo + (hi - lo) // 2
            missing = arr[mid] - mid - 1
            if missing < k:
                lo = mid
            else:
                hi = mid - 1

        if arr[lo] - lo - 1 >= k:
            return k
        else:
            return k + lo + 1

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        counter = 0
        index = 0
        while (k > 0):
            counter += 1
            if index < len(arr) and arr[index] == counter:
                index += 1
            else:
                k -= 1
        return counter

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        if len(arr) == 0:
            return k
        
        ans = 1
        idx = 0
        while k > 0:
            if idx < len(arr) and arr[idx] == ans:
                idx += 1
            else:
                k -= 1 
                if k == 0:
                    break
            ans += 1
            
        return ans

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        if len(arr) == 0:
            return k
        
        i = 1
        s = set(arr)
        while True:
            if i not in s:
                k -= 1 
                if k == 0:
                    return i 
            i += 1 
        
        return -1

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        missing = []
        target = 0
        if len(arr) == arr[-1] :
            target = k + arr[-1] 
        else:
            for n in range(1, arr[-1]+2):
                missing.append(n)
            for m in arr:
                missing.remove(m)
            if k > len(missing):
                target = missing[-1] + k - len(missing)
            else:
                target = missing[k-1]
            
        return target

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        if arr[0] > k: return k
        counts = arr[0]-1
        for i in range(1, len(arr)):
            gap = arr[i]-arr[i-1]-1
            if gap == 0: continue
            if counts+gap >= k: return arr[i-1]+k-counts
            else: counts += gap
        return arr[-1]+k-counts
            
            


class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        if arr[0] > k: return k
        else: k = k - arr[0] + 1
        for index in range(1, len(arr)):
            if k > (arr[index] - arr[index-1] - 1):
                k = k - (arr[index] - arr[index-1] - 1)
            else:
                return arr[index-1] + k
        if k > 0:
            return arr[-1] + k


class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        def bsearch(arr, val):
            low, high = 0, len(arr)-1
            while low <= high :
                mid = (low+high) // 2
                if arr[mid] < val:
                    low = mid + 1
                elif arr[mid] > val:
                    high = mid - 1 
                else:
                    return mid
            return -1
        count = 0
        max_int = max(arr)
        for i in range(1, max_int + k +1):
            if bsearch(arr, i) == -1:
                count += 1
                print(i)
            if count == k:
                return i
        
        


class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        x = [i for i in range(1,arr[-1] + 1)]
        for i in arr:
            if i in x:
                x.remove(i)
        for i in range(k):
            x.append(arr[-1]+i+1)
        return x[k-1]

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        
        preNum = 0
        missNum = 0
        for currNum in arr:
            preMissNum = missNum
            missNum += currNum - preNum - 1
            if missNum >=k:
                res = preNum + k - preMissNum
                return res
            preNum = currNum
            
        res = preNum + k - missNum
        return res
        
        
        
                
            


class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        real=list(range(1,arr[-1]+k+1))
        missing=sorted(list(set(real)-set(arr)))
        return missing[k-1]

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        n_miss = 0
        i = 0
        c = 1
        n = len(arr)
        while n_miss < k:
            if i < n and arr[i] == c:
                c += 1
                i += 1
            else:
                c += 1
                n_miss += 1
        return c - 1

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        
        counter = set()
        for i in arr:
            counter.add(i)
        
        position = 0
        i = 1
        while True:
            if i not in counter:
                position += 1
                
            if position == k:
                return i
            
            i += 1

            
            


class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        
        t=list(set([i for i in range(1,3000)])-set(arr))
        t.sort()
        return t[k-1]
        
        
                
            


class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        
        new_arr = []
        
        l = len(arr)
        
        last = arr[-1]
        
        map_num = {}
        
        for i in range(l):
            
            map_num[arr[i]] = 1
        
        for i in range(1,last+2):
            if i not in map_num:
                new_arr.append(i)
                
        print(new_arr)
                
        if len(new_arr) == 0:
            return last+k
        
        elif k > len(new_arr):
            return new_arr[-1] + k - len(new_arr) 
        
        else:
            return new_arr[k-1]
        
        
                
            


class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        def binary_search(t):
            lo = 0
            hi = len(arr)
            while lo <= hi:
                mid = lo + (hi-lo)//2
                if mid >=len(arr):
                    return False
                if arr[mid] == t:
                    return True

                if arr[mid] > t:
                    hi = mid - 1
                else:
                    lo = mid + 1
            return False
        count = 0
        for num in range(1, arr[-1]+k+1):
            if not binary_search(num):
                count+=1
                if count == k:
                    return num
        return -1

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        if not arr:
            return k

        last = arr[-1]
        for i in range(last):
            if i not in arr:
                if k == 0:
                    return i
                k -= 1


        while k:
            last += 1
            k -= 1

        return last + 1

class Solution:
    def findKthPositive(self, a: List[int], k: int) -> int:
        if len(a) == a[-1]:
            return a[-1]+k
        # print(list(range(a[0],a[-1]+1)))
        # print([x for x in range(1,a[-1]+1) if x not in a])
        t = [x for x in range(1,a[-1]+1) if x not in a]
        if len(t) < k:
            return a[-1] +k-len(t)
        else:
            return t[k-1]


class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        for i in range(1, arr[-1]):
            if i not in arr:
                k -= 1
                if not k:
                    return i
        return arr[-1] + k

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        nums = []
        
        for i in range(1,arr[-1]+1):
            nums.append(i)
            
        for i in range(len(nums)):
            if nums[i] not in arr:
                k-=1
            if k == 0:
                return nums[i]
        
        val = arr[-1]
        while k!=0:
            val+=1
            k-=1
            
        return val
            
            
            
            
    
    
            
            


class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        count = 0
        for i in range(1,arr[-1]+1):
            if i not in arr:
                count += 1
            if count == k:
                return i
        return (arr[-1] - count + k)

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        a2 = arr.copy()
        arr.extend([i for i in range(arr[-1]+1, arr[-1]+1+k)])
        print (a2)
        for i in range(1, a2[-1]+1):
            if i not in arr:
                k-=1
            if k==0:
                return i
        return a2[-1] + k
        # return 0


class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        
        counter = set()
        for i in arr:
            counter.add(i)
        
        result = []
        
        position = 1
        while k > 0:
            if position not in counter:
                k -= 1 
            position += 1
            
        return position - 1
            
            


class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        last = arr[-1]
        new = []
        for i in range(1,last):
            if i not in arr:
                new.append(i)
        
        if len(new) >= k:
            return new[k-1]
        else:
            end = k-len(new)
            return last + end

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        
        res = []
        
        for i in range(1,arr[-1]):
            if i not in arr:
                res.append(i)
        
        if len(res) == 0 or len(res) < k:
            return arr[-1]+k-len(res)
        else:
            return res[k-1]

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:

        n = arr[-1]
        x = 0
        count = 0
        for i in range(1,n+1):
            
            if i not in arr:
                count+=1
                if count == k:
                    x = i
        if x == 0:
            x =(k-count) + n
            
        return x
        
        


class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        
        missing_arr = [x+1 for x in range(arr[-1]+1) if x+1 not in arr ]
        #print(missing_arr)
        n = len(missing_arr)
        if k>n:
            return missing_arr[-1]+k-n
        return missing_arr[k-1]


class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        r=[]
        t=0
        i=1
        while len(r)<k:
            if i not in arr:
                t+=1
                r.append(i)
            i+=1
        return r[-1]

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        x = 1
    
        count = 0
        while count !=k:
            if x not in arr:
                count = count+1
                if count ==k:
                    return x
            x = x+1
                


class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        
        index = 0
        count = 1
        counter = 0
        
        while True:
            
            
            if not count in arr:
                counter += 1
                if counter == k:
                    return count
            index += 1
            count += 1


class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        missing_count=1
        while k!=0:
            if missing_count not in arr:
                k-=1
                missing_count+=1
            else:
                missing_count+=1
        return missing_count-1


class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int: # good 2, check the diff between idx and element, then compare to k, time O(logn), space O(1)
        l, r = 0, len(arr)-1
        while l<r: # find the last idx whose diff from the num is <k+1 
            m = (l+r)//2
            if arr[m]-m>=k+1:
                r = m-1
            else:
                l = m+1
        
        if arr[l]-l < k+1: 
            return l+k+1 # arr[l]+(k+1)-(arr[l]-l)
        else:
            return l+k # arr[l-1]+(k+1)-(arr[l-1]-l+1)


class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        n = 0
        for i in list(range(1, arr[-1]+k+1)):
            if i not in arr:
                n += 1
                if k == n:
                    return i

arr = [2,3,4,7,11]
k = 5

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        return [x for x in range(1,len(arr)+k+1) if x not in arr][k-1]
                
                    
                    
solution = Solution() 
solution.findKthPositive(arr, k)

        


class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        high=arr[-1]
        for i in range(1,high+1):
            if(i not in arr):
                k-=1
            if(k==0):
                return i
        if(k>0):
            return high+k


class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        it_arr = []
        i = 1
        while len(it_arr) < k+1:
            if i not in arr:
                it_arr.append(i)
            i += 1
        return it_arr[k-1]

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        
        missing = []
        #print(len(arr)+k)
        for num in range(1,len(arr)+k+1):
            #print(num)
            if num not in arr:
                missing.append(num)
        
        #print(missing)
        return missing[k-1]

class Solution:
    def findKthPositive(self, a: List[int], k: int) -> int:
        if len(a) == a[-1]:
            return a[-1]+k
        print((list(range(a[0],a[-1]+1))))
        print([x for x in range(1,a[-1]+1) if x not in a])
        t = [x for x in range(1,a[-1]+1) if x not in a]
        if len(t) < k:
            return a[-1] +k-len(t)
        else:
            return t[k-1]


class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        x=[]
        for i in range(1,1000):
            while len(x)<=k:
                if i not in arr:
                    x.append(i)
                i=i+1
        print(x)
        return x[k-1]


class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        l = max(arr) + k
        com = [i for i in range(1,l+1) if i not in arr]
        return com[k-1]
                


class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:

        n = arr[-1]
        x = 0
        count = 0

    
        for i in range(1,n+1+k):
            if i not in arr:
                count+=1
                if count == k:
                    x = i
            
        return x
        
        


class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int: # good 2, check the diff between idx and element, then compare to k, time O(logn), space O(1)
        l, r = 0, len(arr)-1
        while l<r: # find the first idx whose diff from the num is >=k+1 
            m = (l+r)//2
            if arr[m]-m>=k+1:
                r = m
            else:
                l = m+1
        
        if arr[l]-l < k+1: # cannot find within the range of the arr
            return l+k+1 # arr[l]+(k+1)-(arr[l]-l), l=n-1 actually
        else: # can find
            return l+k # arr[l-1]+(k+1)-(arr[l-1]-l+1)


class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        
        a = [i for i in range(1, arr[-1] + k + 10)]
        return [i for i in a if i not in arr][k - 1]

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        integer = list(range(1, max(arr)+k+1))
        result = []
        while(len(result) < k):
            for i in integer:
                if i not in arr:
                    result.append(i)
        return result[k-1]


class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        standard = []
        for i in range(1, arr[-1]+k+1):
            standard.append(i)
        # print(standard)
        
        diff = []
        for i in standard:
            if i not in arr:
                diff.append(i)
        # print(diff)
        
        return diff[k-1]

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        l = max(arr) + k
        com = [i for i in range(1, l+1)]
        diff = [x for x in com if x not in arr]
        return diff[k-1]


class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        count = 1
        while k >0:
            if count not in arr:
                k = k -1 
                print(k)
            count += 1
        return count -1
            
       
            


class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        m=arr[-1]
        s={}
        for i in range(m+k+1):
            if i not in arr:
                s[i]=1
        return list(s.keys())[k]

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        m=max(arr)
        a=[]
        for i in range(1,m+k+1):
            if i not in arr:
                a.append(i)
        a=sorted(a)
        return a[k-1]

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        vec = []
        numbers = [x+1 for x in range(max(arr)+k)]
        for x in numbers:
            if x not in arr:
                vec.append(x)
        return vec[k-1]

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        l = []
        x = 1
        for i in range(k+max(arr)):
            if x not in arr:
                l.append(x)
                x += 1
            else:
                x += 1
        return l[k-1]

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        
        o = []
        ptr = 0
        for n in range(1, arr[-1]):
            if ptr < len(arr) and n != arr[ptr]:
                o.append(n)
            else:
                ptr += 1
                    
        if k > len(o):
            return arr[-1] + k - len(o)
        else:
            return o[k - 1]

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        q=[]
        p= max(arr) + k
        for i in range(1,p+1):
            if i not in arr:
                q.append(i)
        print(q)
        
        return(q[k-1])
                


class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        i = 1
        arr1 = []
        while(len(arr1)<=k):
            if i not in arr:
                arr1.append(i)
                i = i+ 1
            else:
                i+=1
        print(arr1)
        return arr1[k-1]
            


class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        cur=0
        i=1
        while cur<k:
            if arr.count(i)==0:
                cur=cur+1
                res=i
            i=i+1
        return res    

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        expected_value = 1
        i = 0
        while i < len(arr) and k > 0:
            if arr[i] != expected_value:
                k -= 1
            else:
                i += 1

            expected_value += 1

        while k > 0:
            expected_value += 1
            k -= 1

        return expected_value - 1


class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        if not arr:
            return k

        start = 1
        i = 0

        while i < len(arr):
            print(start, arr[i])
            if k == 0:
                return start - 1
            if start != arr[i]:
                k -= 1
                start += 1
            elif start == arr[i]:
                start += 1
                i += 1

        if k > 0:
            return start + k - 1

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        res = list(range(1,2001))
        res = list(set(res) - set(arr))
        print(res)
        return res[k-1]