Writing an algorithm for this question. Please refer to the attached picture. In

Question

Writing an algorithm for this question. Please refer to the attached picture.

In class we looked at an algorithm to determine whether or not an array contained duplicate values. This is a related problem. You are to write an algorithm that takes an array of integers as input and whose output is an array that contains the values in the input array with the duplicates removed. That is, each distinct value in the input array should appear once and only once in the output array. The order of values in the original array does not have to be preserved in the output array. Write your algorithm using pseudo-code and document it comments. Determine the running time of your algorithm using O notation, as a function of the size of the input array, n. There are marks assigned to efficiency so the faster your algorithm runs, the better your grade. Input: {1, 2, 3, 4, 5) -output {1, 2, 3, 4, 5} Input: {4, 1 5, 4, 2, 7, 4, 2) -output {4, 1, 5, 2, 7} Input: {12, 3, 12, 12, 12} -output {12, 3}

Explanation / Answer

calculating the space complexity of the removing duplicate elements from array of elements

It is not possible to delete all duplicates from a sorted list faster than O(n) time unless you have some other information about the list. You have to look at each item at least one to see what value it has. If you do not do that, we could make two of the items you're not looking at duplicates of each other, and you would have no way of knowing, since you didn't look at those items.

One example of a special sorted list where you could find any constant number of duplicate items is one with all numbers [a,b] with some constant number of duplicated items. We can look at any two positions and figure out how many duplicates there are in between by comparing the numbers with their positions in the array.

Consider this list:

1 2 3 4 4 5 6
There's one duplicate element. By looking at 1 and 6 we know that there should be the numbers 1 2 3 4 5 6 in between them, but there's one slot too many between them, so there must be at least one duplicate. Continue by splitting the list in half by looking at the middle element, the first 4.

1 _ _ 4 _ _ 6
The first half has 4 items and by comparing the numbers at position 1 and position 4, we know that there cannot possibly be any duplicates there.

Between 4 and 6, however, we have 2 slots. Thus there must be a duplicate 4, 5 or 6.

1 _ _ 4 4 _ 6
There's our duplicate, in O(log n) time and O(1) (extra) space.

You can find repeated elements in an array in time complexity O(n) and space complexity O(1) only when you are given limit of elements in array and limit must not exceed the array size. If limit is not given den u have to use another array of size MAX (ele)-MIN(ele)+1.
so suppose u r given array of size n which contains elements of varying from 0 to n-1. u can use the index of elements to find repeated elements.
suppose array is 2,3,4,3,2,6,4 now size is 7 and element limits is 0 to 6.
steps:
1) Iterate the array from 1st element to last.
2) 1st elements is 2 so check element in array with index 2 is >=0 if yes then change the element in array index 2 to -1*ar[abs(ar[i])] and print it.
Check ar[abs(ar[i])]>0 if yes den make it ar[abs(ar[i])]= - ar[abs(ar[i])]

example: 2,3,4,3,2,6,4
for i=0
array will be 2,3,-4,3,2,6,4
for i=1
array will be 2,3,-4,-3,2,6,4
for i-2
array will be 2,3,-4,-3,-2,6,4
for i=3
array will be 2,3,-4,-3,2,6,4 it will print 3
for i=4
array will be 2,3,-4,-3,2,6,4 it will print 2
for i=5
array will be 2,3,-4,-3,2,6,-4
for i=6
array will be 2,3,-4,-3,2,6,-4 it will print 4.

Note: please check the below program for better practical understanding

// program for printing the unique elements in an array

package com;

class FindDuplicate
{
void printRepeating(int arr[], int size)
{
int i;
System.out.println("The repeating elements are : ");
  
for (i = 0; i < size; i++)
{
if (arr[Math.abs(arr[i])] >= 0)
{
   arr[Math.abs(arr[i])] = -arr[Math.abs(arr[i])];
System.out.print(Math.abs(arr[i]) + " ");
}
}   
}

/* Driver program to test the above function */
public static void main(String[] args)
{
   long starttime=System.currentTimeMillis();
   System.out.println(starttime);
FindDuplicate duplicate = new FindDuplicate();
int arr[] = {4, 2, 4, 5, 2, 3, 1};
int arr_size = arr.length;
duplicate.printRepeating(arr, arr_size);
System.out.println();
long endtime=System.currentTimeMillis();
System.out.println(endtime);
long executionTime=endtime-starttime;
System.out.println("Execution time is "+executionTime+" Milliseconds");
}
}

output:

The repeating elements are :
4 2 5 3 1
1496639072959
Execution time is 1 Milliseconds

// same program in c

#include <stdio.h>
#include <stdlib.h>

void printRepeating(int arr[], int size)
{
int i;
printf("The repeating elements are: ");
for (i = 0; i < size; i++)
{
if (arr[abs(arr[i])] >= 0)
   {
   arr[abs(arr[i])] = -arr[abs(arr[i])];
   printf(" %d ", abs(arr[i]));
   }
  
  
}
}

int main()
{
int arr[] = {1, 2, 3, 1, 3, 6, 6};
int arr_size = sizeof(arr)/sizeof(arr[0]);
printRepeating(arr, arr_size);
getchar();
return 0;
}

// another program for removing elements based on sets this program is apt for long range of value this program is for removing duplicates in array either sorted or unsorted list

package com;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;
import java.util.stream.Collectors;

public class RemoveDuplicatesInArray {

   public static void main(String args[])
   {
       long startTime=System.currentTimeMillis(); // calculating the starting time of program
       System.out.println("startTime:"+startTime+"Milli Seconds");
       Scanner s=new Scanner(System.in);
       System.out.println("Enter the Size of Aray");
       int n=s.nextInt(); // declaring the array size
       int arr[]=new int[n];
       System.out.println("Enter the array elements including duplicates"); // reading the elements into array based on user input
       for(int i=0;i<n;i++)
       {
           arr[i]=s.nextInt();
       }
      
       System.out.println("Enter array elements are "); // printing the array elements
       for(int i=0;i<n;i++)
       {
           System.out.print(arr[i]+" ");
       }
       System.out.println();
       Set<Integer> myset=Arrays.stream(arr).boxed().collect(Collectors.toSet()); // converting the array to set because if we store the elements in a set it doesn't accept duplicates so by we can remove the duplicates from an array.
       System.out.println(myset);
       long endtime=System.currentTimeMillis(); // finding the endtime of program in milli
       System.out.println("endtime"+endtime+"milli seconds");
       long executionTime=endtime-startTime; // calculating the executionTime
       System.out.println("executionTime"+executionTime+"milli seconds");
      
   }
}

output:
-------
startTime:1496639231566Milli Seconds
Enter the Size of Aray
3
Enter the array elements including duplicates
1 1 3
Enter array elements are
1 1 3
[1, 3]
endtime1496639237231milli seconds
executionTime5665milli seconds

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.