Your algorithm can use any algorithm and data structure that we learned in class

Question

Your algorithm can use any algorithm and data structure that we learned in class. You are given an array of n integers. Design an algorithm Find A - Pair to find all unique pairs of elements (x, y) whose summation is S. Your algorithm must run in O(n log n) time. You are given multiple arrays of strings, where different string may have different numbers of characters. Design an algorithm Make-A-Set running in O(n log n) time, where the algorithm returns an union set of strings by combining all arrays and removing any duplicates. Suppose we have an array of n positive integers range from 0 to n - 1. Design an algorithm that sorts the array in O(n) time.

Explanation / Answer

1)
Step 1: Sort the Array that will take nlog n time
Step 2: Take two indices i and j , i starts from first element of array and j points to last element of array i.e
i = 1 , j = n, run loop until i<j
Step 3:  Check if Array[i] + Array[j] == Sum if Yes Print arr[i] and arr[j] found
Step 3: Else if Check Array[i] + Array[j] > Sum if Yes then we need to reduce our sum so make j = j-1
Step 4: Else if Check Array[i] + Array[j] < Sum if Yes then we need to increase our sum so make i = i+1
Step 5: Go to Step 2

Step 6: END


3) Take Extra space of size n , like count[n]

Step 1 : Run a loop from 1 to n for all the array elements
Step 2: Do count[arr[i]] ++, So that at that particlar index wwe will have the count which will say how many time an array value has appeare and array value is i in count array
Step 3: Once it is done, run a loop 1 count array and print the indexi if count is 1 other wise print index k times if count is k

Step 4: We Will see that Array elements is sorted in ascending order


Time taken O(n) as we made only one scan to our array and space taken is O(n)

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

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