arrayscfor-loopnested-loopsfunction-definition

Given an array return any index on which its dominator occurs


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.


Solution

  • 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;
    }