Q. Given an array of size n. It contains numbers in the range 1 to n. Each number is present at least once except for 2 numbers (one is missing and one is repeated)

INPUT               {2,1,3,3,5}  n=5
Missing  one  is  4  and  repeating  one  is  3


It  means  that  one  number  is  missing  and  other  is  repeating  twice  and  we  have  to  find  both  of  them..

METHOD  1

It  is  the  most  obvious  way  to  do  this  which  is  to  sort  them  first  and  then  we  may  be  easily  able to  find  the  remaining  ones...

Time Complexity=O(n logn),,for   merge  sort

Space Complexity=O(n), for  stack  used  in  merge  sort 

METHOD  2

Hash  the  above  elements  and  store  count  as their  values  and  we  may  easily  get  the  answer

METHOD 3

It  is  a  little  tricky  as  it  involves  two  equations  in  this

sum(n)=n(n+1)/2,,

product  of  n=n!

now in  our  given  array  we  will  be  having  sum  as  (sum+repeated-missed)

and  similarly  we  will  have  our  product  as  (product*repeated)/missed

And  hence  we   get  our  two  equations  to  be  solved