Question

1. We have an array A of size n. There are only positive integers in this array. Note that the array may have integers that are not distinct, and it could be any array of positive integers in creation (I like the numbers found the decimal expansion of π for instance). When possible provide the exact complexity of the algorithm. If it’s not possible explain the O/Ω/Θ complexity.

1. Design an efficient algorithm to find the maximum difference between any two integers in the array.

2. Design an efficient algorithm to find the minimum difference between any two integers in the array. If there are multiple minimum differences, you only need to find one.

3. Design an efficient algorithm to find the majority number in the array if it exists. By majority, I mean the number that occurs more than half the time in the array or ⌈(? + 1)/2 ⌉ (there are at least 3 ways that I can think of to approach this).

Answer 1

Question 1.

part (a):-

We can find the maximum difference between any two integer by traversing the array only once . Since all the elements in the array are positive so maximum difference ocuurence when we subtract minimum from maximum.so in one traversal we can find the minimum and maximum element from the array and reurn the maximum-minimum this will take O(n) times where n is the number of elements in the array.

Part(b):-

for finding minimum difference we have to sort the array and compare all adjacents pairs in sorted array and keep track of minimum differences . This algorithm will take O(nlogn) because in sorting it will take O(nlogn) and in find minimum between two adjacent pair it will take O(n) time so overall it will take O(nlogn).

Part (c):-

There are various ways to solve this problem :-

method 1:-

we will count the occurence of every element using two loop. and test if the count for that particular element is greater than (n+1)/2 then output that element as majority element. this will take O(n*n) time.

method 2:-

first of all sort the array and find the and check for the count of mid or (mid+1)th element if there count is greater than (n+1)/2 then output that element as majority element . this will take O(nlogn) for sorting.so overall time complexity is O(nlogn).

method 3:-

we can modify the method 1 using hashing we will count the occurence of every element in the array using hashing and check which element has occurence greater than (n+1)/2 .this will take O(n) time as insertion in hashing will take O(1) time .So overall time complexity is O(n) and also space complexity is O(n) for hashtable.

Note :-

If you have any problem let me know i will try to help you . Thank you.