PLEASE READ THE PROBLEM CAREFULLY! DO NOT WRITE IN JAVA, C, ETC YOU MUST WRITE T

Question

PLEASE READ THE PROBLEM CAREFULLY! DO NOT WRITE IN JAVA, C, ETC
YOU MUST WRITE THIS IN PSEUDOCODE OR ENGLISH. The following requirements are listed, please read the probelm carefully before posting.

Thank you!

Problem 5. Find Duplicates For this problem you are given an array of size n containing non-negative integers. Each integer is from the range [0, n-1 Create an algorithm (English or pseudocode) that finds all duplicates in a given array and then outputs them. Requirements No duplicate values in the output array It is ok if the output is not sorted Your algorithm should work in O(n) time (tight bound). You can't use hashing (in case you were going to). You must explain the complexity of your algorithm

Explanation / Answer

Pseudocode :

step1 : start

step2 : array declaration with duplicate vaues like 3, 4, 3, 4, 3, 2, 5

step3 : find the array size
step4 : calling a function findDuplicates(arr, arr_size);

step5 : control transfer to called function void findDuplicates(int arr[], int size)

step6 : for (i = 0; i < size; i++)

step7 : if (arr[abs(arr[i])] >= 0)

step8 : if sign is positive then make it negative by using the statement arr[abs(arr[i])] = -arr[abs(arr[i])];

step9 : else

step10 : print the elements as duplicate elements using abs(arr[i])

step 11 : stop

Time complexity analysis :

There it runs for O(n) complexity.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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