Instructions . For some problems it may be helpful to use some algorithm covered
ID: 3589833 • Letter: I
Question
Instructions . For some problems it may be helpful to use some algorithm covered in class as a subroutine. · Integers being "very large" means you can't do things like create an array with /entries largest integer valuc, and you can't use lincear-time sorting algorithms like radix sort ·You're also not allowed to use hash tables. » When a problem asks for an "efficient" algorithm, this means you should try to design arn algorithm whose worst-case complexity is as good as possible, but I'm not telling you what the problem's best possible complexity is.Explanation / Answer
The algorithm is based on the below observation:
If we know the majority elements of A[1...n/2] and A[n/2+1..n] if exists and their counts then we can find whether a majority element exists for A[1..n] and its count.
Let a1, a2 be majority elements of A[1...n/2] and A[n/2+1..n] with their counts k1, k2. it wil contain null if there doesn't exists a majority element and count will be 0.
If a1 and a2 both are null then we can easily say there is no majority element for A[1..n] so count is 0.
If a1, a2 are not null and a1==a2 then majority element exists for A[1..n] and it is a1 and count is k1+k2.
If a1, a2 are not null and a1 != a2, then pick the one with the most count and search for it in the other array. that is if k1>k2 then search for a1 in A[n/2+1..n] and get the number of occurrences of it, this can be acheived by comparing each element of A[n/2+1..n] with a1 and incrementing the count if equals, let this count be k3. Now if k1+k3 >= n/2+1 then majority element exists for A[1..n] and its count is k1+k3. Vice versa if k2>k1. Incase k1==k2 then again ther is no majority element for A[1..n].
If a1 is not null and a2 is null, then search for a1 in A[n/2+1..n] and get the number of occurrences of it, let it be k3. Now if k1+k3 >= n/2+1 then majority element exists for A[1..n] and its count is k1+k3. Vice versa if a2 is not null and a1 is null.
Now given the majority elements and their counts for the subarrays of half size, we can find the majorrity element of A[1..n] and its count in O(n) time. So if we apply divide and conquer with above formualtion the complete algorithm with all recursions takes O(nlogn) time.