Need help to solve this using divide and conquer approche please. Add comments o
ID: 3753997 • Letter: N
Question
Need help to solve this using divide and conquer approche please. Add comments on the code please. Also analyze the complexity of it. Thanks
Given an array of size n, find the majority element. The majority element is the element that appears more than You may assume that the array is non-empty and the majority element always exist in the array. Example 1: n/2 J times. Input: [3,2,3] Output: 3 Example 2 Input: [2,2,1,1,1,2,2] output: 2 Seen this question in a real interview before? Yes No 1 int majorityElement(int* nums, int numsSize)Explanation / Answer
/*One way to solve this is by simply using a map but since you have asked for a divide and conquer metthod here it goes ...all cases are being considered for your simplicity...concepts of mergesort and binary search is used to implement it in D&C manner*/
#include<stdio.h>
#define max 1000 //assuming maximum number of elements to be 1000 you can change it as you wish
void main()
{
int n,arr[max],i=0,j=0,c,chk=0;
printf("no. of elements : ");
scanf("%d",&n);
printf(" enter data ");
for(i=0;i<n;i++)
{
scanf("%d",&arr[i]);
}
mergeSort(arr, 0, n-1); //firstly sorting the elements
printf("sorted sequence : ");
for(i=0;i<n;i++) //printing sorted sequence so as to verify our sort
{
printf("%d ",arr[i]);
}printf(" ");
for(j=0;j<n;j++)
{
// printf("inside if");
c=count(arr,n,arr[j]);
if(c>(n-1)/2)
{printf("majority element is : %d ",arr[j]);
chk++;
break;}
}
if(chk==0)
printf("No majority element !");
}
void merge(int arr[], int l, int m, int r) //using the merge function for mergesorting
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(int arr[], int l, int r)
{
if (l < r)
{
int m = l+(r-l)/2;
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
}
int count(int array[],int size,int key) //counts the occurence of key acc to start and last indices
{
int f,l,c;
f=first(array,size,key);
l=last(array,size,key);
c=l-f+1;
return c;
}
int last(int array[],int size,int key) //gives the index of given key where it appears last in the array
{
int l,h,mid,found=-1;
l=0;
h=size-1;
while(l<=h)
{
mid=(l+h)/2;
if(array[mid]==key)
{
found=mid;
l=mid+1;
}
else
if(array[mid]<key)
l=l+1;
else h=h-1;
}
return found;
}
int first(int array[],int size,int key) //gives the index of given key where it appears first in the array
{
int l,h,mid,found=-1;
l=0;
h=size-1;
while(l<=h)
{
mid=(l+h)/2;
if(array[mid]==key)
{
found=mid;
h=mid-1;
}
else
if(array[mid]<key)
l=l+1;
else h=h-1;
}
return found;
}
/* Time Complexity will be =O(nlogn)
because of merge sort */