Codility - Dominator - Java  

by ne on 2022-02-16 under Algo/DS/Problems tagged with codility

Hi,
The problem description is in the comments above the solution below.

The problem belongs to Codility, you can try out it yourself on their platform.


import java.util.*;
/**
 * An array A consisting of N integers is given. The dominator of array A is the value that occurs in more than half of the elements of A.
 *
 * For example, consider array A such that
 *  A[0] = 3    A[1] = 4    A[2] =  3
 *  A[3] = 2    A[4] = 3    A[5] = -1
 *  A[6] = 3    A[7] = 3
 *
 * The dominator of A is 3 because it occurs in 5 out of 8 elements of A (namely in those with indices 0, 2, 4, 6 and 7) and 5 is more than a half of 8.
 *
 * Write a function
 *
 *     class Solution { public int solution(int[] A); }
 *
 * that, given an array A consisting of N integers, returns index of any element of array A in which the dominator of A occurs. The function should return −1 if array A does not have a dominator.
 *
 * For example, given array A such that
 *  A[0] = 3    A[1] = 4    A[2] =  3
 *  A[3] = 2    A[4] = 3    A[5] = -1
 *  A[6] = 3    A[7] = 3
 *
 * the function may return 0, 2, 4, 6 or 7, as explained above.
 */
public class Dominator {
    public int solution(int[] A) {
        if(A.length ==0) return -1;
        if(A.length==1) return 0;
        Stack st = new Stack<>();
        st.push(0);
        for(int i=1;i 0 && A[i] != A[st.peek()]){
                st.pop();
            }else{
                st.push(i);
            }
        }

        if(st.size()>0) {
            int count =0;
            int p = st.pop();
            for(int i=0;i A.length/2) {
                return p;
            }else{
                return -1;
            }
        }
        else
            return -1;
    }
    public static void main(String... args){
        System.out.println(new Dominator().solution(new int[]{2,1,1,3}));
        System.out.println(new Dominator().solution(new int[]{2,1,1,3,4}));
        System.out.println(new Dominator().solution(new int[]{3,4,3,2,3,-1,3,3}));
    }

}