You are given an array arr[] of N integers including 0. The task is to find the smallest positive number missing from the array.
Example 1:
Input:
N = 5
arr[] = {1,2,3,4,5}
Output: 6
Explanation: Smallest positive missing 
number is 6.
Example 2:
Input:
N = 5
arr[] = {0,-10,1,3,-20}
Output: 2
Explanation: Smallest positive missing 
number is 2.
Your Task:
The task is to complete the function missingNumber() which returns the smallest positive missing number in the array.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
Constraints:
1 <= N <= 10^{6}
-10^{6} <= arr[i] <= 10^{6}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Complete search

Starter code: #User function Template for python3



class Solution:

    

    #Function to find the smallest positive number missing from the array.

    def missingNumber(self,arr,n):

        #Your code here

Solutions:
class Solution:

	def missingNumber(self, arr, n):
		d = {}
		for i in range(1, max(arr) + 1):
			d[i] = 0
		for i in arr:
			if i > 0:
				d[i] += 1
		for (key, values) in d.items():
			if values == 0:
				return key
		return max(arr) + 1


class Solution:

	def missingNumber(self, arr, n):
		z = set(arr)
		for i in range(1, n + 2):
			if i in z:
				continue
			else:
				return i


class Solution:

	def missingNumber(self, arr, n):
		for i in range(0, n):
			while arr[i] > 0 and arr[i] <= n and (arr[i] != arr[arr[i] - 1]):
				temp = arr[i]
				(arr[i], arr[temp - 1]) = (arr[temp - 1], arr[i])
		for i in range(0, n):
			if arr[i] != i + 1:
				return i + 1
		return n + 1


class Solution:

	def missingNumber(self, arr, n):
		for i in range(n):
			if arr[i] % 10000000 > 0 and arr[i] % 10000000 <= n:
				if arr[arr[i] % 10000000 - 1] < 0:
					arr[arr[i] % 10000000 - 1] = 0
				arr[arr[i] % 10000000 - 1] += 10000000
		res = n + 1
		for i in range(0, n):
			if arr[i] < 10000000:
				res = i + 1
				break
		return res


class Solution:

	def missingNumber(self, arr, n):
		arr.sort()
		s = 1
		for i in range(0, len(arr)):
			if s == arr[i]:
				s += 1
		return s


class Solution:

	def missingNumber(self, arr, n):
		s = set(arr)
		for i in range(1, n + 2):
			if i not in s:
				return i


class Solution:

	def missingNumber(self, arr, n):
		k = 0
		c = 0
		m = []
		p = 0
		arr.sort()
		for y in range(len(arr)):
			if arr[y] > 0:
				m.append(arr[y])
			else:
				p += 1
		m = set(m)
		m = list(m)
		m.sort()
		for i in range(1, len(m) + 1):
			if i != m[k]:
				c += 1
				return i
				break
			else:
				k += 1
		if c == 0 and p != len(arr):
			return max(arr) + 1
		if p == len(arr):
			return 1


class Solution:

	def missingNumber(self, arr, n):
		n = len(arr)
		j = 0
		for i in range(n):
			if arr[i] <= 0:
				(arr[i], arr[j]) = (arr[j], arr[i])
				j += 1
		positive_nums = arr[j:]
		for num in positive_nums:
			index = abs(num) - 1
			if index < len(positive_nums) and positive_nums[index] > 0:
				positive_nums[index] = -positive_nums[index]
		for i in range(len(positive_nums)):
			if positive_nums[i] > 0:
				return i + 1
		return len(positive_nums) + 1


class Solution:

	def missingNumber(self, arr, n):
		arr = list(set(arr))
		arr.sort()
		s = 0
		ind = 0
		k = 1
		for i in range(0, len(arr)):
			if arr[i] >= 0:
				s = arr[i]
				ind = i
				break
		if s == 0:
			k = 0
		for j in range(ind, len(arr)):
			if arr[j] != k:
				return k
			k += 1
		return k


class Solution:

	def missingNumber(self, arr, n):
		index = 0
		count = 0
		for index in range(n):
			correct_index = arr[index] - 1
			while correct_index >= 0 and correct_index < n and (arr[index] != arr[correct_index]):
				(arr[correct_index], arr[index]) = (arr[index], arr[correct_index])
				correct_index = arr[index] - 1
		for i in range(n):
			if arr[i] != i + 1:
				return i + 1
		return n + 1


class Solution:

	def missingNumber(self, arr, n):
		arr.sort()
		ans = 1
		for i in range(n):
			if ans == arr[i]:
				ans += 1
			elif arr[i] > ans:
				break
		return ans


class Solution:

	def missingNumber(self, arr, n):
		s = {}
		for i in range(1, max(arr) + 1):
			s[i] = 0
		for i in arr:
			if i > 0:
				s[i] += 1
		for i in s:
			if s[i] == 0:
				return i
		return max(arr) + 1


class Solution:

	def missingNumber(self, arr, n):
		res = 0
		i = 0
		while i < n:
			if arr[i] > 0:
				(arr[i], arr[res]) = (arr[res], arr[i])
				res += 1
			i += 1
		for i in range(res):
			if abs(arr[i]) - 1 >= res:
				continue
			if arr[abs(arr[i]) - 1] < 0:
				continue
			arr[abs(arr[i]) - 1] *= -1
		i = 0
		while i < res:
			if arr[i] > 0:
				return i + 1
			i += 1
		return i + 1


class Solution:

	def missingNumber(self, arr, n):
		arr = set(arr)
		i = 1
		for i in range(1, max(arr)):
			if i not in arr:
				return i
		return max(arr) + 1


class Solution:

	def missingNumber(self, arr, n):
		li = list(set(arr))
		li.sort()
		j = 1
		for i in range(n):
			if li[i] >= 1:
				if li[i] > j:
					return j
				j = j + 1
		if max(li) < 0:
			return 1
		else:
			return max(li) + 1


class Solution:

	def missingNumber(self, arr, n):
		dic = {}
		for i in range(1, 10 ** 5 + 1):
			dic[i] = 1
		for i in arr:
			dic[i] = 0
		for i in dic.keys():
			if dic[i] == 1:
				return i


class Solution:

	def missingNumber(self, arr, n):
		for i in range(n):
			if arr[i] < 0:
				arr[i] = 0
		for i in range(n):
			val = abs(arr[i])
			if 1 <= val <= n:
				if arr[val - 1] > 0:
					arr[val - 1] *= -1
				elif arr[val - 1] == 0:
					arr[val - 1] = -1 * (n + 1)
		for i in range(1, n + 1):
			if arr[i - 1] >= 0:
				return i
		return n + 1


class Solution:

	def missingNumber(self, arr, n):
		shift = self.segregate(arr, n)
		return self.findMissingPositive(arr[shift:], n - shift)

	def segregate(self, arr, n):
		j = 0
		for i in range(n):
			if arr[i] <= 0:
				(arr[i], arr[j]) = (arr[j], arr[i])
				j += 1
		return j

	def findMissingPositive(self, arr, n):
		for i in range(n):
			if abs(arr[i]) - 1 < n and arr[abs(arr[i]) - 1] > 0:
				arr[abs(arr[i]) - 1] = -arr[abs(arr[i]) - 1]
		for i in range(n):
			if arr[i] > 0:
				return i + 1
		return n + 1


class Solution:

	def missingNumber(self, arr, n):
		numSet = set(arr)
		num = 1
		for i in range(len(arr) + 1):
			if num in numSet:
				num += 1
		return num


class Solution:

	def missingNumber(self, arr, n):
		distinct = set(arr)
		i = 1
		idx = 0
		while True:
			if i not in distinct:
				return i
			i += 1
			idx += 1
			if idx == n:
				break
		return i


import numpy as np

class Solution:

	def missingNumber(self, arr, n):
		k = 1000001
		ref = np.zeros(k)
		for i in range(n):
			if arr[i] > 0:
				ref[arr[i]] = 1
		for i in range(k):
			if ref[i + 1] == 0:
				return i + 1
				break


class Solution:

	def missingNumber(self, arr, n):
		miss = 1
		arr.sort()
		for i in range(n):
			if arr[i] == miss:
				miss += 1
		return miss


class Solution:

	def missingNumber(self, arr, n):
		for i in range(len(arr)):
			if 1 > arr[i] or arr[i] > n:
				arr[i] = 0
		for i in range(len(arr)):
			if arr[i] > 0:
				arr[(arr[i] - 1) % n] += n
		for i in range(len(arr)):
			arr[i] //= n
			if arr[i] == 0:
				return i + 1
		return n + 1


class Solution:

	def missingNumber(self, arr, n):
		arr = set(arr)
		arr = list(arr)
		arr.sort()
		if 1 in arr:
			ind0 = arr.index(1)
			arr[:] = arr[ind0:]
			for i in range(n - ind0):
				if arr[i] != i + 1:
					return i + 1
			else:
				return i + 2
		else:
			return 1


class Solution:

	def missingNumber(self, arr, n):
		missing_num = None
		lst = [0 for x in range(0, n + 2)]
		for i in arr:
			if i > 0:
				try:
					lst[i] = i
				except:
					pass
		missing_num = lst[1:].index(0) + 1
		return missing_num


class Solution:

	def missingNumber(self, arr, n):
		s = set(arr)
		i = 1
		while True:
			if i not in s:
				return i
			i += 1


class Solution:

	def missingNumber(self, arr, n):
		m = max(arr)
		if m < 1:
			return 1
		if len(arr) == 1:
			return 2 if arr[0] == 1 else 1
		l = [0] * m
		for i in range(n):
			if arr[i] > 0:
				if l[arr[i] - 1] != 1:
					l[arr[i] - 1] = 1
		for i in range(len(l)):
			if l[i] == 0:
				return i + 1
		return i + 2


class Solution:

	def missingNumber(self, arr, n):
		arr = set(arr)
		arr = sorted(list(arr))
		c = 0
		for i in range(n):
			if arr[i] <= 0:
				continue
			elif c + 1 == arr[i]:
				c = c + 1
				continue
			else:
				return c + 1
		return c + 1


class Solution:

	def missingNumber(self, arr, n):
		d = {}
		for i in arr:
			if i > 0:
				if i not in d:
					d[i] = 1
				else:
					d[i] += 1
		for i in range(1, n + 1):
			if i not in d:
				return i
		return n + 1


class Solution:

	def missingNumber(self, arr, n):
		positives = [x for x in arr if x > 0]
		n = len(positives)
		for i in range(n):
			if abs(positives[i]) - 1 < n and positives[abs(positives[i]) - 1] > 0:
				positives[abs(positives[i]) - 1] = -positives[abs(positives[i]) - 1]
		for i in range(n):
			if positives[i] > 0:
				return i + 1
		return n + 1


class Solution:

	def missingNumber(self, arr, n):
		present = [False for _ in range(n + 1)]
		for i in range(n):
			if 0 < arr[i] <= n:
				present[arr[i]] = True
		for i in range(1, n + 1):
			if not present[i]:
				return i
		return n + 1


class Solution:

	def missingNumber(self, arr, n):
		c = 1
		a = sorted(arr)
		for i in a:
			if i > c:
				return c
			elif i == c:
				c += 1
		return c


class Solution:

	def missingNumber(self, arr, n):
		arr.sort()
		a = 1
		for i in arr:
			if i > 0 and i > a:
				return a
			elif i == a:
				a += 1
		return a


class Solution:

	def missingNumber(self, arr, n):
		arr.sort()
		if 0 in arr:
			arr = set(arr)
			arr = list(arr)
			count = 1
			ind = arr.index(0)
			for i in range(ind + 1, n):
				if arr[i] != count:
					return count
				count += 1
		else:
			arr = set(arr)
			arr = list(arr)
			if 1 not in arr:
				return 1
			else:
				ind = arr.index(1)
				count = 1
				for i in range(ind, n):
					if arr[i] != count:
						return count
					count += 1
		return max(arr) + 1


class Solution:

	def missingNumber(self, arr, n):
		for i in range(n):
			ele = arr[i] - 1
			while 1 <= arr[i] <= n and arr[i] != arr[ele]:
				(arr[i], arr[ele]) = (arr[ele], arr[i])
				ele = arr[i] - 1
		for i in range(n):
			if i + 1 != arr[i]:
				return i + 1
		return n + 1


class Solution:

	def missingNumber(self, nums, n):
		for i in range(n):
			while nums[i] > 0 and nums[i] <= n and (nums[nums[i] - 1] != nums[i]):
				(nums[nums[i] - 1], nums[i]) = (nums[i], nums[nums[i] - 1])
		for i in range(n):
			if nums[i] != i + 1:
				return i + 1
		return n + 1


class Solution:

	def missingNumber(self, arr, n):
		arr.sort()
		smallest = 1
		for i in range(n):
			if arr[i] > 0:
				if arr[i] == smallest:
					smallest += 1
		return smallest


class Solution:

	def missingNumber(self, arr, n):
		from collections import defaultdict
		dic = defaultdict(int)
		for i in arr:
			dic[i] += 1
		for i in range(1, n + 2):
			if dic[i] == 0:
				return i


class Solution:

	def missingNumber(self, arr, n):
		j = n - 1
		for i in range(n):
			if arr[i] < 1 or arr[i] > n:
				while j >= 0 and (arr[j] < 1 or arr[j] > n):
					j -= 1
				if j <= i:
					break
				(arr[i], arr[j]) = (arr[j], arr[i])
				j -= 1
				if j <= i:
					break
		if j < 0:
			return 1
		for i in range(j + 1):
			arr[arr[i] % n - 1] = arr[arr[i] % n - 1] + n
		for i in range(j + 1):
			if arr[i] <= n:
				return i + 1
		return i + 2


class Solution:

	def missingNumber(self, arr, n):
		i = 0
		j = 1
		while True:
			while i < n and arr[i] > 0:
				i += 1
			j = max(i + 1, j)
			while j < n and arr[j] <= 0:
				j += 1
			if i < n and j < n:
				(arr[i], arr[j]) = (arr[j], arr[i])
				i += 1
				j += 1
			else:
				break
		arr = arr[:i]
		for i in range(len(arr)):
			j = abs(arr[i]) - 1
			if j >= 0 and j < len(arr):
				arr[j] = -abs(arr[j])
		for i in range(len(arr)):
			if arr[i] > 0:
				return i + 1
		return len(arr) + 1


class Solution:

	def swap(self, start, end, A, val):
		A[end] = val
		A[start] = 0

	def missingNumber(self, A, N):
		result = A[N - 1] + 1
		A.sort()
		for i in range(N):
			if A[i] == i + 1:
				continue
			elif A[i] <= 0 or A[i] >= N:
				A[i] = 0
			else:
				self.swap(i, A[i] - 1, A, A[i])
		for i in range(N):
			if A[i] == 0:
				result = i + 1
				break
		return result


class Solution:

	def missingNumber(self, arr, n):
		freq = [0] * (10 ** 6 + 1)
		for num in arr:
			if num > 0:
				freq[num] += 1
		for i in range(1, len(freq)):
			if freq[i] == 0:
				return i
		return -1


class Solution:

	def missingNumber(self, arr, n) -> int:
		j = 0
		for i in range(n):
			if arr[i] <= 0:
				(arr[i], arr[j]) = (arr[j], arr[i])
				j += 1
		arr = arr[j:]
		n = n - j
		for i in range(n):
			if abs(arr[i]) <= n and arr[abs(arr[i]) - 1] > 0:
				arr[abs(arr[i]) - 1] = -arr[abs(arr[i]) - 1]
		for i in range(n):
			if arr[i] > 0:
				return i + 1
		return n + 1


class Solution:

	def missingNumber(self, arr, n):
		s = set()
		for i in range(n):
			if arr[i] >= 0:
				s.add(arr[i])
				continue
		arr.clear()
		for ele in s:
			arr.append(ele)
		arr.sort()
		if len(arr) == 0:
			return 1
		if len(arr) == 1 and arr[0] != 1:
			return 1
		if len(arr) == 1 and arr[0] == 1:
			return 2
		x = 0
		for j in range(len(arr) - 1):
			if arr[j] + 1 != arr[j + 1]:
				x = arr[j] + 1
				break
		if arr[0] > 1:
			return 1
		elif x == 0:
			return arr[-1] + 1
		else:
			return x


class Solution:

	def missingNumber(self, arr, n):
		a = []
		for i in range(n + 1):
			a.append('x')
		for i in range(n):
			if arr[i] >= 0 and arr[i] <= n:
				a[arr[i]] = arr[i]
		for i in range(1, n + 1):
			if a[i] == 'x':
				return i
		return a[-1] + 1


class Solution:

	def missingNumber(self, arr, n):
		arr.sort()
		m = 0
		for i in arr:
			if i < 0:
				continue
			if i > m + 1:
				return m + 1
			else:
				m = i
		return arr[-1] + 1


class Solution:

	def missingNumber(self, arr, n):
		ptr = 0
		for i in range(n):
			if arr[i] == 1:
				ptr = 1
				break
		if ptr == 0:
			return 1
		for i in range(n):
			if arr[i] <= 0 or arr[i] > n:
				arr[i] = 1
		for i in range(n):
			arr[(arr[i] - 1) % n] += n
		for i in range(n):
			if arr[i] <= n:
				return i + 1
		return n + 1


class Solution:

	def missingNumber(self, arr, n):
		arr = [x for x in sorted(set(arr)) if x > 0]
		n = len(arr)
		for i in range(n):
			if i + 1 != arr[i]:
				return i + 1
		return n + 1


class Solution:

	def missingNumber(self, arr, n):
		dic = {}
		for elem in arr:
			dic[elem] = True
		for i in range(1, n + 2):
			if dic.get(i, False) == False:
				return i


class Solution:

	def missingNumber(self, arr, n):
		vis = set(arr)
		i = 1
		while i in vis:
			vis.add(i)
			i += 1
		return i


class Solution:

	def missingNumber(self, arr, n):
		arr.sort()
		c = 0
		for i in range(0, n):
			if arr[i] < 0:
				continue
			elif c + 1 == arr[i]:
				c = c + 1
				continue
		else:
			return c + 1