Question

Given an array, A, of n−2 unique integers in the range from 1 to n, describe an O(n)-time method for finding the two integers in the range from 1 to n that are not in A. You may use only O(1) space in addition to the space used by A.

Answer 1

Hi
Please find the working Python code for the given problem, pass the list that contains the n-2 integers and this function will return the list of missing intergers.
Time Complexity = O(n+n) = O(n)
Space Complexity = O[1] as we have used the same list to do our operation, just appended two more values to the list i.e O[1]

PLEASE UPVOTE IF YOU LIKE THE ANSWER

Thanks

def findMissingIntegers(A):
   A += [0,0]
   n = len(A)
   itr = 0
   while(itr < n):
       idx = A[itr] - 1
       #need to swap idx and itr values
       tmp = A[itr]
       A[itr] = A[idx]
       A[idx] = tmp
       itr += 1
#after running the above loop all values wiill come to its respective place   
   missingIntegers = []
   for i,a in enumerate(A):
       if a == 0:
           missingIntegers.append(i+1)
   return missingIntegers