Assume you have an array A[1. . n] of n elements. A majority element of A is any
ID: 3884463 • Letter: A
Question
Assume you have an array A[1. . n] of n elements. A majority element of A is any element occurring in more than n/2 positions (so if n = 6 or n = 7, any majority element will occur in at least 4 positions). Assume that elements cannot be ordered or sorted, but can be compared for equality. (You might think of the elements as chips, and there is a tester that can be used to determine whether or not two chips are identical.) Design an efficient divide and conquer algorithm to find a majority element in A (or determine that no majority element exists).
Explanation / Answer
For the completion of task, we will apply divide and conquer approach.
Procedure find_Majority_Element (A[1..n])
Input: Array A of objects
Output: Majority element of A
IF n=2 then
IF A[1]=A[2] then
return A[1]
EndIF
EndIF
ELSE
return No Majority Element Found
ENDELSE
Create a temporary array temp
FOR i=1 to n:
IF A[i] = A[i+1] then
Insert A[i] into temp
ENDIF
i=i+1
EndFOR
return find_Majority_Element (temp)
End Procedure
Procedure CheckSanity(A[1...n])
Input: Array A of objects
Output: Majority element of A
P = find_Majority_Element (A[1...n])
frequency= find_Frequency(A[1...n],P)
IF frequency > (n/2) + 1 then
return P
ENDIF
ELSE
return No Majority Element Found
ENDELSE
END Procedure
// function find_Frequency computes the number of an element appears in the given array A[1..n]
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.