## DEV Community is a community of 892,765 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

dev.to staff

Posted on

# 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 (17)

Empereol

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;
}
``````
kesprit • Edited on

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
}
``````
Michael Kohl • Edited on

Ruby.

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

`.tally` is the best!

Alvaro Montoro • Edited on

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;
}
``````
Vidit Sarkar

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;
}
``````
Andreas Jakof • Edited on

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;

}
``````
mushtaqasif

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
``````
Amin • Edited on

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;
}
``````
Shannon Crabill • Edited on

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
``````
Nicholas ―M― • Edited on

Here's my solution in JavaScript. I'm not sure how to embed Gists, but here is the link to it .... 😥

Nicholas ―M―

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.

Michael Kohl

New in 2.7 😊

Gabi • Edited on

Java: