Lesson 6: Dominator (Dominator)

Lesson 6: Dominatorhttps://codility.com/programmers/lessons/6

This solution also utilizes the O(N) algorithm to find a leader described in the reading material that Codility provides. First read it briefly.
Open reading material (PDF)

Indeed, the definition of 'dominator' in this problem is the same as  'leader'. So we can use the same algorithm as the previous problem of `equi leader' 
(http://codility-lessons.blogspot.tw/2015/02/lesson-6-equileader.html)

This gives the 100% score as below.

#include <alloca.h>

int solution(int A[], int N) {
    
    //first find the leader and count its occurances.
    //as all the values on the stack will be the same,
    //we only have to keep one value.
    int sp = 0;
    int candidate = 0;
    
    int i;
    for (i = 0; i < N; i++){
        if (sp == 0){
            sp++;
            candidate = A[i];
            continue;
        }
        
        if (candidate == A[i]){
            sp++;
        }
        else {
            sp--;
        }
    }
    
    //if there is no dominator, return -1
    if (sp == 0){
        return -1;
    }
    
    //now we check if the candidate value is really a dominator
    int cnt = 0;
    for (i = 0; i < N; i++){
        if (A[i] == candidate){
            cnt++;
        }
    }
    
    //if there is no dominator, return -1.
    if (cnt <= N / 2){
        return -1;
    }
    
    //now we have a leader.
    int dominator = candidate;
  
    
    //let's find the first dominator in the array
    for (i = 0; i < N; i++){
        if (A[i] == dominator){
            return i;
        }
    }
    
    //the code won't reach here since we have a dominator. 
    return -1;
}

However, it should be noted that we don't have to scan the array after finding a dominator; we can return any of the place where the dominator is found, returning the last index is also okay.

#include <alloca.h>

int solution(int A[], int N) {

    

    //first find the leader and count its occurances.

    //as all the values on the stack will be the same,

    //we only have to keep one value.

    int sp = 0;

    int candidate = 0;

    int lastIndex = 0;

    

    int i;

    for (i = 0; i < N; i++){

        if (sp == 0){

            sp++;

            candidate = A[i];

            lastIndex = i;

            continue;

        }

        

        if (candidate == A[i]){

            sp++;

            lastIndex = i;

        }

        else {

            sp--;

        }

    }

    

    //if there is no dominator, return -1

    if (sp == 0){

        return -1;

    }

    

    //now we check if the candidate value is really a dominator

    int cnt = 0;

    for (i = 0; i < N; i++){

        if (A[i] == candidate){

            cnt++;

        }

    }

    

    if (cnt > N / 2){

        return lastIndex;

    }

    

    //if there is no dominator, return -1

    return -1;

}