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

Source: leetcode | Difficulty: EASY
Tags: Sorting

Data structures

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
			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
		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:
		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:
		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


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]
		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:
		(l, r) = (0, len(arr) - 1)
		while l < r:
			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
		else:
			return l + k


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:
		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 = []
		for num in range(1, len(arr) + k + 1):
			if num not in arr:
				missing.append(num)
		return missing[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:
		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)
		diff = []
		for i in standard:
			if i not in arr:
				diff.append(i)
		return diff[k - 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]