- Arrays, Natural Numbers, Pattern Searching, permutation

Find all numbers in range [1, N] that are not present in given Array

Given an array arr[] of size N, where arr[i] is natural numbers less than or equal to N, the task is to find all the numbers in the range [1, N] that are not present in the given array.Examples:Input: arr[ ] = {5, 5, 4, 4, 2}Output: 1 3Explanation: For all numbers in the range [1, 5], 1 and 3 are not present in the array.Input: arr[ ] = {3, 2, 3, 1}Output: 4Naive Approach: The simplest approach is to hash every array element using any data structure like the dictionary and then iterate over the range [1, N] and print all numbers not present in the hash.dTime Complexity: O(N)Auxiliary Space: O(N)Approach: The above approach can be optimized further by marking the number at position arr[i] – 1, negative to mark i is present in the array. Then print all positions of the array elements that are positive as they are missing. Follow the steps below to solve the problem:Iterate over the array, arr[] and for each current element, num perform the following steps:Update arr[abs(num)-1] to -abs(arr[abs(num)-1]).Iterate over the array, arr[] using the variable i, and print the i+1 if arr[i] is positive.Below is the implementation of the above approach:Python3  def getMissingNumbers(arr):          for num in arr:                  arr[abs(num)-1] = -(abs(arr[abs(num)-1]))          for pos, num in enumerate(arr):                  if num > 0:            print(pos + 1, end =’ ‘)    arr = [5, 5, 4, 4, 2]  getMissingNumbers(arr)Time Complexity: O(N)Auxiliary Space: O(1)Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.  To complete your preparation from learning a language to DS Algo and many more,  please refer Complete Interview Preparation Course.In case you wish to attend live classes with experts, please refer DSA Live Classes for Working Professionals and Competitive Programming Live for Students.