Question

Problem 1: [10 Marks] Given a generic array with ‘n’ items (not only integers). Give a solution for checking whether there are any duplicate elements in the array or not? You just need to return a boolean (true or false). State the complexity of your solution. Can you come up with another solution that has O(n logn) complexity? Explain.

Problem 2: [10 Marks] Now consider the same problem as problem 1, but this time you only have positive integer numbers ranging from 0 to (n-1) in the array. Can you find a duplicate in O(n) complexity? Implement the solution.

Plz answer 2nd only

Answer 1

2.

// Algorithm to check if an array of n positive integers ranging from 0 to (n-1) contains duplicate elements

Let the input array be arr[n]
Create an array of length n to contain the frequency of elements in arr and initialize all its elements to 0
   int counts[n] ; // array index starts from 0 and ends at (n-1), the elements are initialized to 0
   // loop that will continue for a maximum of n times
   for(i=0;i<n;i++)
       counts[i] = 0
Loop over the input array, incrementing th counts of elements in counts array
  
   // loop that will continue for a maximum of n times
   for(i=0;i<n;i++)
   do
       counts[arr[i]] = counts[arr[i]] + 1; // since arr contains elements from 0 to n-1 , the element at arr[i] will not exceed the index of counts
       // if counts of arr[i] element > 1 then duplicate elements is present, return true
       if((counts[arr[i]]) > 1) then
           return true
       end if  
   done      
  
return false; // no duplicate elements present in arr
      
     
Both the loops in the solution continues for a maximum of n times. The solution only contains a single loop that runs for a maximum of n times. Hence, the time complexity of the above solution is O(n).