3. Divide and Conquer (6 points) Let A[0..n -1| be an array of n numbers. A numb

Question

3. Divide and Conquer (6 points) Let A[0..n -1| be an array of n numbers. A number in A is a majority element if A contains this number at least Ln/2 + 1 times. So for example, the array A 4, 3, 2,4,1,3,3,6, 3,3, 3,3} has 3 as its majority element. Write a divide-and-conquer algorithm that determines whether a given array A[0..n 1] contains a majority element, and if so, returns it. Your algorithm should run in O(n log n) time. You are not allowed to simply sort the array. Set up and solve a runtime recurrence for your algorithm Hint: Start by applying the generic divide-and-conquer approach. Try to divide by two. Then try to combine the results. From the given runtime you should be able to guess how much time you are allowed to spend for dividing and combining.

Explanation / Answer

/* Below is the program to find the majority element that satisfies no. of element = (size/2) + 1 */
# include<stdio.h>
# define bool int

int findKey(int *, int);
bool isMajorityTrue(int *, int, int);

/* Method to display Majority Element */
void printMajorityElement(int a[], int size)
{
/* Find the key for Majority*/
int keyElement = findKey(a, size);

/* Print the key if it is Majority*/
if (isMajorityTrue(a, size, keyElement))
printf(" %d ", keyElement);
else
printf("No Majority Element");
}

/* Method to search the key for Majority */
int findKey(int a[], int size)
{
int maj_index = 0, count = 1;
int i;
for (i = 1; i < size; i++)
{
if (a[maj_index] == a[i])
count++;
else
count--;
if (count == 0)
{
maj_index = i;
count = 1;
}
}
return a[maj_index];
}

/* Method to check if the key occurs more than n/2 times */
bool isMajorityTrue(int a[], int size, int keyElement)
{
int i, count = 0;
for (i = 0; i < size; i++)
if (a[i] == keyElement)
count++;
if (count > size/2)
return 1;
else
return 0;
}

/* Main method that will run to test above functions */
int main()
{
int a[] = {1, 3, 3, 3, 3, 1, 2};
int size = (sizeof(a))/sizeof(a[0]);
printMajorityElement(a, size);
getchar();
return 0;
}

/*Please rate this question, if you get your question solved. Thanks*/

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

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