# Codility ‘Dominator’ Solution

##### Short Problem Definition:

Find an index of an array such that its value occurs at more than half of indices in the array.

Dominator

##### Complexity:

expected worst-case time complexity is O(N);

expected worst-case space complexity is O(1)

##### Execution:

As explained in the training material…

##### Solution:
```def solution(A):
candidate_ele = ''
candidate_cnt = 0

for value in A:
if candidate_ele == '':
candidate_ele = value
candidate_cnt = 1
else:
if value != candidate_ele:
candidate_cnt -= 1
if candidate_cnt == 0:
candidate_ele = ''
else:
candidate_cnt += 1

if candidate_cnt == 0:
return -1

cnt = 0
last_idx = 0

for idx, value in enumerate(A):
if value == candidate_ele:
cnt += 1
last_idx = idx

if cnt > len(A)//2:
return last_idx

return -1
```

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

• Nico
• Tanuj Sharma
• M. Rahil Rafiq

java Solution (100 out of 100 points )

public static int solution(int[] A){
int arrLength = 0;
arrLength = A.length;
if(arrLength == 0) return -1;
int temp=0;
List list = null;
Map<Integer, List> valMap = new HashMap<Integer, List>();
for(int i = 0; i < A.length; i++){
temp = A[i];
if(valMap.containsKey(temp)){
list = new ArrayList();
list = valMap.get(temp);
valMap.put(temp, list);
}else{
list = new ArrayList();
valMap.put(temp, list);
}

}
int maxValKey = 0;
int valuCount = 0;
for(Map.Entry<Integer, List> val : valMap.entrySet()){
if(valuCount < val.getValue().size()){
valuCount = val.getValue().size();
maxValKey = val.getKey();
}
}

//Check if values of repeating number is greater than half of the array
double halfVal = (A.length)/2;
double valueofMax = valuCount;
if(halfVal < valueofMax){
return valMap.get(maxValKey).get(0);
}else{
return -1;
}

}