I am posting this question 4th time and I am not getting correct answer. I promi
ID: 3757402 • Letter: I
Question
I am posting this question 4th time and I am not getting correct answer. I promise I will rate you if i get correct answer. Please help me to solve this problem. I have to use Leetcode to answer this question and leetcode already provides main method so i do not need main method in my code.
Need help to solve this using divide and conquer, also add comments on the code so I can understand what's going on and also complexity in terms of big O.
Given an array of size n, find the majority element. The majority element is the element that appears more than n/2 times. You may assume that the array is non-empty and the majority element always exist in the array.
Here is the starting of the code in C. I need help to solve using this method please.
int majorityElement(int* nums, int numsSize) {
Explanation / Answer
/* Hi, I am writing two approaches. Hope it will help */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
/*
* To use divide and conquer, you can use quick sort .
* worst case time complexity is
*/
int comparator (const void *a, const void *b)
{
return (*(int *)a - *(int *)b);
}
int majorityElement (int *num, int numSize)
{
/* For divide and conquer I am using qsort here. quick sort is divide and conquer algo
* The time complexity is in worst case O(n*n)
*/
int i;
int count =0, maxCount = 0, val=0;
qsort((void*)num, numSize, sizeof(num[0]), comparator);
#if 0 /*For debugging*/
for (i=0; i<numSize; i++)
{
printf ("%d ", num[i]);
}
printf (" ");
#endif
/*This loop will take O(n)*/
for (i=0; i<numSize - 1; i++)
{
//printf (" %d %d %d ", num[i], num[i+1], count);
if (num[i] == num[i+1])
{
count++;
}
else
{
if (count > maxCount )
{
maxCount = count;
val = num[i];
//printf (" %d %d ", maxCount, i);
}
count =0;
}
}
if (count >maxCount)
val = num[i];
/*So the total time complexity is O(N*N + N) = O(N*N)*/
return val;
}
int main() {
int arr[] = {1, 1, 2, 3, 1, 1, 5, 6, 1, 1, 1, 1, 1,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6 };
int size = sizeof (arr)/ sizeof (arr[0]);
printf ("%d ", majorityElement (arr, size));
return 0;
}
#if 0
/*This is an alternative approach, which is not using divide and conquer
* The complexity is o(n*n) */
int majorityElement (int *num, int numSize)
{
int i = 0, j = 0;
int count = 0;
for (i=0; i<numSize; i++)
{
count = 0;
for (j=0; j<numSize; j++)
{
if (num[i] == num[j])
{
count ++;
}
}
if (count > numSize/2)
break;
}
return num[i];
}
#endif
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.