# Daily Challenge #220 - What Dominates Your Array?

An array arr consisting of n integers is given. The dominator of arr is the value that occurs in more than half of the elements of arr.

Write a function dominator(arr) that returns the dominator of arr. The function should return −1 if array does not have a dominator. All values in arr will be >=0.

For example, consider the array such that arr = [3,4,3,2,3,1,3,3]
The dominator of arr is 3 because it occurs in 5 out of 8 elements of arr and 5 is more than half of 8.
dominator([3,4,3,2,3,1,3,3]) => 3
dominator([1,2,3,4,5]) => -1

Tests:
dominator([3,4,3,2,3,1,3,3])
dominator([1,1,1,2,2,2]),
dominator([1,1,1,2,2,2,2])

Good luck!

This challenge comes from joh_pot on CodeWars. Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge idea for a future post? Email yo+challenge@dev.to with your suggestions!

### Discussion TypeScript

/**
* Return the dominator of the given array.
*
* The dominator is the value that occurs in more than half of the elements of
* the given array.
*
* @param nums Array of numbers.
*
* @returns -1 if there is no dominator.
*
* @example
* dominator([3,4,3,2,3,1,3,3]) → 3
* dominator([1,2,3,4,5])       → -1 // No val occurs more than half the array
*/
function dominator(nums: number[]): number {
for (const item of new Set(nums)) {
if (nums.filter(i => i === item).length > nums.length / 2) {
return item;
}
}

return -1;
}


Ruby.

def dominator(arr)
arr.tally.find { |_k, v| v > arr.size / 2 }&.first || -1
end


.tally method , cool

New in 2.7 😊

.tally is the best!

Swift solution :

func dominator(_ arr: [Int]) -> Int {
arr.reduce(into: (dominator: -1,record: 0)) { (occur, currentNumber) in
let numberOfTime = arr.filter { $0 == currentNumber }.count if numberOfTime > arr.count / 2 && numberOfTime > occur.1 { occur.dominator = currentNumber occur.record = numberOfTime } }.dominator } dominator([3,4,3,2,3,1,3,3]) // 3 dominator([1,1,1,2,2,2]) // -1 dominator([1,1,1,2,2,2,2]) // 2  And hardcore version : func dominator(_ arr: [Int]) -> Int { (arr.reduce(into: [(Int,Int)]()) { (result, i) in result.append((i, arr.filter({ i ==$0 }).count ))
}
.sorted { $0.1 >$1.1 }
.first { \$0.1 > arr.count / 2 })?.0 ?? -1
}


Not tested (written on the phone) but should do the trick
C#

public static int GetDominator(IEnumerable<int> arr)
{
var num = arr.Count()/2;
return arr.GroupBy( x => x)
.Where(x => x.Count() > num)
.OrderByDesc(x => x.Count()) //in case there are more than one
.FirstOrDefault()? //pick the one most often or null, if there are none
.First() ?? -1;

}


A solution in JavaScript:

const dominator = arr => {
const indexes = {};

for (let x = 0; x < arr.length; x++) {
indexes[arr[x]] = indexes[arr[x]] ? indexes[arr[x]] + 1: 1;
if (indexes[arr[x]] > arr.length / 2) return arr[x];
}

return -1;
}


JavaScript

/**
* Return the integer that occurs more than half of the size of an array
*
* @param {number[]} numbers The array of integers.
*
* @throws {Error}      If the function gets called with not exactly one argument.
* @throws {TypeError}  If the first argument is not an array.
* @throws {TypeError}  If the first argument is not an array of integers.
*
* @return {number} -1 if there is no dominator
*
* @example
* console.log(dominator([3,4,3,2,3,1,3,3]));  // 3
* console.log(dominator([1,1,1,2,2,2]));      // -1
* console.log(dominator([1,1,1,2,2,2,2]));    // 2
*/
function dominator(numbers) {
if (arguments.length !== 1) {
throw new Error("Expected one argument.");
}

if (!Array.isArray(numbers)) {
throw new TypeError("Expected first argument to be an array.");
}

const occurrences   = {};
const threshold     = numbers.length / 2;

for (const number of numbers) {
if (!Number.isInteger(number)) {
throw new TypeError("Expected first argument to be an array of integers.");
}

if (occurrences[number]) {
occurrences[number]++;
} else {
occurrences[number] = 1;
}

if (occurrences[number] > threshold) {
return number;
}
}

return -1;
}


The edge cases made this one tricky. Here's a working function in Ruby without using Tally

def dominator(arr)
baseline = arr.length / 2

# Tally how many times each n is in the array
# Sort by value
# Delete any entries where the value is less than or equal to the baseline (half the length of the array)
# Put values in order, largest to smallest
# Turn it back into a hash

result = arr.inject(Hash.new(0)) { |memo, item|
memo[item] += 1;
memo
}.sort_by{|key,value| value}.delete_if {|key, value| value <= baseline }.reverse.to_h

result != {} ? result.values.first : -1

end



Results

dominator([3,4,3,2,3,1,3,3]) #> 5
dominator([1,1,1,2,2,2]) #> -1
dominator([1,1,1,2,2,2,2]) #> 4


Go Soultion

package main

import "fmt"

func dominator(arr []int) int {
numCount := make(map[int]int)

for _, num := range arr {
numCount[num]++

if numCount[num] > len(arr)/2 {
return num
}
}

return -1
}

func main() {
for _, list := range [][]int{
{3, 4, 3, 2, 3, 1, 3, 3},
{1, 2, 3, 4, 5},
{3, 4, 3, 2, 3, 1, 3, 3},
{1, 1, 1, 2, 2, 2},
{1, 1, 1, 2, 2, 2, 2},
} {
fmt.Printf("%v => %d\n", list, dominator(list))
}
}


output:

[3 4 3 2 3 1 3 3] => 3
[1 2 3 4 5] => -1
[3 4 3 2 3 1 3 3] => 3
[1 1 1 2 2 2] => -1
[1 1 1 2 2 2 2] => 2


C++ solution

int dominator(vector<int> arr){
// stores the number with its count
unordered_map<int, int> numCount;

// if count of any number becomes more than arr.size()/2
// then return that number
for(int num : arr){
if(++numCount[num] > arr.size()/2)
return num;
}

// if no number has count more than arr.size()/2
// then return -1
return -1;
}


Doing this taught me about Array.prototype.some. I originally wanted to use .forEach, but needed a way to break out of the loop once we found the dominator -- no need to keep processing once the answer has been found, especially if the scenario was an array of something ridiculous, like 15,000 items.

Ruby

def dominator(arr)
arr.each.with_object(hash = Hash.new(0)) { |value,dict| dict[value] += 1 }
hash.each { |k,v| return k if 2*v > arr.size}
-1
end  