dev.to staff

Posted on Apr 7, 2020

Daily Challenge #220 - What Dominates Your Array?

#challenge

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!

Top comments (12)

Empereol • Apr 7 '20

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 • Apr 7 '20 • Edited

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
}

Alvaro Montoro • Apr 8 '20 • Edited

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 • Apr 7 '20

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 • Apr 7 '20 • Edited

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 • Apr 7 '20

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 • Apr 7 '20 • Edited

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 • Apr 7 '20 • Edited

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― • Apr 7 '20 • Edited

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

Nicholas ―M― • Apr 7 '20

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.

Shannon Crabill • Apr 7 '20

.tally is the best!

View full discussion (12 comments)

DEV Community

Daily Challenge #220 - What Dominates Your Array?

Top comments (12)

Read next

Jakarta EE, Java & Jboss compatibility.

Upgrade do MongoDB - o guia definitivo.

Shallow Knowledge vs. Deep Knowledge: The Key to Standing Out in Today’s Tough Job Market

Tic-tac-toe: I thought this post would never come...