In an array example program add a method called removeDuplic

In an array example program, add a method called removeDuplicate() that removes duplicates from a previously sorted array without disrupting the order of index. When a duplicate element is found, the discovered element is then replaced by zero. For example, if the elements of the array are: 2 7 1 1 4 6 1 3 9 2 After the array is sorted, (you may use any simple sorting algorithm for this part): 1 1 1 2 2 3 4 6 7 9 After the duplicates are removed the elements of the array are: 1 0 0 2 0 3 4 6 7 9 What is the Big(O) of removing duplicates operation? Add another method called. removeDuplicateWithShift() that removes the duplicate and shift the element to an empty index. For example, if the elements of the array are: 2 7 1 1 4 6 1 3 9 2 After the array is sorted, (you may use any simple sorting algorithm for this part): 1 1 1 2 2 3 4 6 7 9 After the duplicates are removed the elements of the array are: 1 2 3 4 6 7 9 0 0 0 What is the Big(O) of removing duplicates operation?

Solution

1)

-> In removeDuplicate() mehtod ,for a sorted array , the repeated elements should be replaced by zeros without changing its index.

i.e 1 1 1 2 2 3 3 6 7 9 -> 1 0 0 2 0 3 0 6 7 9

=> the logic for this implementation is :

removeDuplicate(int array[],int lengthofarray)

{

for(i=0;i<lengthofarray;i++) //O(lengthofarray)

{

if(array[i]==array[i+1]) //O(1)

{

temp=array[i]; //O(1)

}

if(temp==array[i+1])   //O(1)

{

array[i+1]=0; //O(1)

}

}

}

-> Since single for loop is enough to replace all sorted repeative elements by zero takes O(n) time where n is length of array.remaining all instructions either O(1) or O(2) .

Therefore the method removeDuplicate() has time complexity O(n)

2)

-> In removeDuplicateWithShift() method,for a sorted array , the repeated elements should be replaced by zeros and shifted elements to last of the arrray.

i.e 1 1 1 2 2 3 3 6 7 9 -> 1 2 3 6 7 9 0 0 0 0

=> the logic for this implementation is :

removeDuplicateWithShift(int array[],int lengthofarray)

{

for(i=0;i<lengthofarray;i++) //O(lengthofarray)

{

if(array[i]==array[i+1]) //O(1)

{

temp=array[i]; //O(1)

}

if(temp==array[i+1])   //O(1)

{

array[i+1]=0; //O(1)

}

}

for(i=0;i<n;i++) //O(n)
{
if(array[i+1]==0) //O(1)
{
for(j=i+1;array[j]==0&&j<n-1;j++); //O(n)
array[i+1]=array[j]; //O(1)
}

array[j]=0; //O(1)

  
}

}

-> Since one for loop and two for loops(one outer and one inner) are used to replace all sorted repeative elements by zero and put all zeros at end of the array takes O(n) and O(n²⁾ time complexitywhere n is length of array.remaining all instructions either O(1) or O(2) .

Therefore the method removeDuplicateWithShift() has time complexity O(n²)