Dominator is a value which occurs on more than half positions in an array. For instance in the array: [3, 4, 3, 2, 3, -1, 3, 3] the value 3 occurs in 5 out of 8 positions. 5/8 > 0.5, so 3 is a dominator: in this array the dominator occurs on indexes : 0, 2, 4, 6 , 7. How to write a function that given an array returns any index on which its dominator occurs. If there is no dominator, the function should return -1.
Tried to solve it using C as:
int arrdominator(int *A,int N)
{
int i,j,idx=0,val=0,cnt=1;
//I thought I would sort the array and then cound the dominating value instances,
qsort(A,N,sizeof(A[0]),sort_fn_ascend);
for(i=0;i<(N-1);i++)
{
for(j=i+1;j<N;j++)
{
if(A[i] == A[j])
{
cnt++;
i++;
break;
}
}
}
}
But i could not get to a solution of finding the dominator value in the array and then return its index.
Thanks to @DocBrown's pointers got my initial code refined to get it working alright:
int arrdominator(int *A,int N)
{
int i,j,idx=0,cnt=1,valmaxseq,dominantval=0;
int *newA = (int*)malloc(sizeof(int)*N);
for(i=0;i<N;i++)
newA[i] = A[i];
qsort(newA,N,sizeof(A[0]),sort_fn_ascend);
for(j=0;j<(N-1);j++)
{
if(newA[j] == newA[j+1])
{
cnt++;
}
else
{
if(cnt > (N/2))
{
valmaxseq = newA[j];
dominantval = 1;
}
cnt = 1;
}
}
//find index of dominant value if there is one
if(dominantval == 1)
for(i=0;i<N;i++)
{
if(A[i] == valmaxseq)
return i;
}
return -1;
}