CODEWITHSUNDEEP
c
goldenmean
goldenmean

Reputation: 18966

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.

Upvotes: 1

Views: 3341

Answers (4)

Clodagh
Clodagh

Reputation: 1

What do you think of this? I've just thought of using the count algorithm in C++. So my answer would be:

int denominator(const vector<int> &A)
{
    int vecSize = A.size();
    //test for empty vec
    if (vecSize ==0)
        return -1;

    //count number of elements in vec then check if count > size/2
    for (int i = 0; i < vecSize; i++)
    {
        int c = count(A.begin(), A.end(), A[i]);
        if (c > vecSize/2)
            return i;
    }

    return -1; //denominator not found
}

Upvotes: 0

goldenmean
goldenmean

Reputation: 18966

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

Upvotes: 3

nana
nana

Reputation: 4481

I will show you how to do it in Python which reads almost like english. You will still have to rewrite it to C, so it is not technically cheating ;)

array_of_numbers = [3, 4, 3, 2, 3, -1, 3, 3]
array_length = len(array_of_numbers)
highest_count_value = 0
highest_count = 0
for each_number in array_of_numbers:
    each_count = array_of_numbers.count(each_number)
    if each_count > highest_count:
        highest_count_value = each_number
        highest_count = each_count

highest_count_value_indices = []
for each_index, each_number in enumerate(array_of_numbers):
    if each_number == highest_count_value:
        highest_count_value_indices.append(each_index)

highest_count_value_is_dominator = True if highest_count > (array_length / 2.0) else False

print("Array: "+`array_of_numbers`)
print("Possible dominator: "+`highest_count_value`)
print("Possible dominator count: "+`highest_count`)
print("Is it dominator? : "+`highest_count_value_is_dominator`)
print("Indices of dominator: "+`highest_count_value_indices`)

There are better and faster ways to achieve this, but I tried to stick to simple methods, so it reads almost as meta programming.

Also the part about returning -1 if there is no dominator is simple enough at this point, right?

Upvotes: 2

Doc Brown
Doc Brown

Reputation: 20044

I am not going to solve this for you, you should really do this on you own, but here are some hints:

  • first, since your spec says you must either return an array of indexes (or -1), I suggest you change the signature of your function accordingly

  • second, you should split up the task into parts. First part (after sorting): determine the length of the longest sequence of equal numbers (and the repeated number of this sequence). Then, test if the sequence if longer than N/2. If so, find out the indexes where the number occurs and return this result. Since you are going to solve this by sorting, make sure you keep a copy of the original array since you will need it to determine the original indexes.

  • if cnt is for counting the sequence length, you must reset it to zero every time you start counting a new sequence. And you will need a second variable maxSequenceLength to keep the length of the longest sequence found so far, as well as a third one valOfMaxSequence.

Hope this helps.

Upvotes: 7

Related Questions