Codility - Dominator - Java
by ne on 2022-02-16 under Algo/DS/Problems tagged with codility
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}));
}
}