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; }