Dominator

Find an index of an array such that its value occurs at more than half of indices in the array
ℹ️ © Codility, 2009-2018

Problem

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 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.

Assume that:
n is an integer within the range [0 … 100,000];
• each element of array A is an integer within the range [-2,147,483,648 … 2,147,483,647].

Complexity:
• expected worst-case time complexity is O(n);
• expected worst-case space complexity is O(1), beyond input storage (not counting the storage required for input arguments).

Solution

C#

using System;
using System.Collections.Generic;
class Solution {
  public int solution(int[] A) {
    Dictionary<int, int> D = new Dictionary<int, int>();
    foreach (int a in A) {
      if (D.ContainsKey(a)) {
        D[a]++;
      } else {
        D.Add(a, 1);
      }
    }
    int n = A.Length; 
    foreach (KeyValuePair<int, int> d in D) {
      if (d.Value > n / 2) {
        return Array.IndexOf(A, d.Key);
      }
    }
    return -1;
  }
}

Java

import java.util.*;
class Solution {
  public int solution(int[] A) {
    Map<Integer, Integer> D = new HashMap<Integer, Integer>();
    for (int a : A) {
      if (D.containsKey(a)) {
        D.put(a, D.get(a) + 1);
      } else {
        D.put(a, 1);
      }
    }
    int n = A.length; 
    for (Map.Entry<Integer, Integer> d : D.entrySet()) {
      if (d.getValue() > n / 2) {
        for (int i = 0; i < n; i++) {
          if (A[i] == d.getKey()) {
            return i;
          }
        }
      }
    }
    return -1;
  }
}

JavaScript

function solution(A) {
  let D = {};
  for (let i in A) {
    let a = A[i];
    if (a in D) {
      D[a]++;
    } else {
      D[a] = 1;
    }
  }
  let n = A.length;
  for (let i in D) {
    let d = D[i];
    if (d > n / 2) {
      return A.indexOf(parseInt(i));
    }
  }
  return -1;
}

PHP

function solution($A) {
  foreach ($A as $a) {
    if (array_key_exists($a, $D)) {
      $D[$a]++;
    } else {
      $D[$a] = 1;
    }
  }
  $n = count($A);
  foreach ($D as $i => $d) {
    if ($d > $n / 2) {
      return array_search($i, $A);
    }
  }
  return -1;
}