DEV Community

Daily Challenge #35 - Find the Outlier

dev.to staff on August 07, 2019

In this challenge, you'll be given an array with a length of at least three, containing (possibly quite large) integers. The array is either compri...
Collapse
 
dance2die profile image
Sung M. Kim • Edited

JavaScript 😀

Not efficient, as it's iterating the array twice (I could've used reduce to iterate once but well... this looks more readable)

BTW, the last one looks weird, as it contains only even numbers.

const isEven = n => n % 2 === 0
const isOdd = n => n % 2 === 1
const findOutlier = arr => {
    const odds = arr.filter(isOdd)
    const evens = arr.filter(isEven)
    return odds.length < evens.length ? odds[0] : evens[0]
}
[
  [2, 4, 0, 100, 4, 11, 2602, 36],
  [160, 3, 1719, 19, 11, 13, -21],
  [4, 8, 15, 16, 24, 42],
  [16, 6, 40, 66, 68, 28]
].map(findOutlier)

demo

Collapse
 
wheatup profile image
Hao • Edited

There's a potential bug.

-21 will fail both isOdd and isEven function.

The function isOdd should be

const isOdd = n => n % 2 !== 0

Since negative odd numbers mod 2 equals to -1 instead of 1.

Collapse
 
dance2die profile image
Sung M. Kim • Edited

Whoa.... you've just caught years worth of bugs I have possibly created... 😅

Thank you @Hao for finding the issue. 😀
I really didn't think that thru. 👍

Here is the updated code

let isEven = n => n % 2 === 0
let isOdd = n => n % 2 !== 0
const findOutlier = arr => {
    const odds = arr.filter(isOdd)
    const evens = arr.filter(isEven)
    return odds.length < evens.length ? odds[0] : evens[0]
}
[
  [2, 4, 0, 100, 4, 11, 2602, 36],
  [160, 3, 1719, 19, 11, 13, -21],
  [4, 8, 15, 16, 24, 42],
  [16, 6, 40, 66, 68, 28],
  [-21, 1, 2, 3]
].map(findOutlier)

updated result

I think I would probably use !isEven next time 😎

Collapse
 
vince_tblt profile image
Vincent Thibault

You only need to fetch the firsts 3 items to know what you are searching for.

function findOutlier (list: number[]): number | void {
  const search = list.slice(0,3).filter(v => v % 2).length > 1 ? 0 : 1;
  return list.find(v => v % 2 === search);
}
Collapse
 
databasesponge profile image
MetaDave 🇪🇺

I have done a Ruby one, based on counting the number of even values in the first three elements of the array to switch the logic between finding the first even and the first odd element.

[
  [2, 4, 0, 100, 4, 11, 2602, 36],
  [160, 3, 1719, 19, 11, 13, -21],
  [4, 8, 15, 16, 24, 42],
  [16, 6, 40, 66, 68, 28]
].map do |array|
  case array.first(3).select(&:even?).size
    when 1 
      array.find(&:even?)
    else 
      array.find(&:odd?)
  end
end

=> [11, 160, 15, nil] 
Collapse
 
easyaspython profile image
Dane Hillard • Edited

This goes through the list of numbers only a single time, stopping early if possible. Could probably be code golfed further 😛

def find_outlier(nums):
    odds = evens = 0
    for num in nums:
        is_even = num % 2 == 0
        is_odd = not is_even

        odds += 1 if is_odd else 0
        evens += 1 if is_even else 0

        # Two of one kind prove the other kind is the outlier
        if (odds > 1 and is_even) or (evens > 1 and is_odd):
            return num
Collapse
 
bauripalash profile image
Palash Bauri 👻

Atleast it works somehow 😅

given = [2, 4, 0, 100, 4, 11, 2602, 36] #input array
odds = evens = 0

if given[0]%2 == 0:
    evens  += 1
else:
    odds += 1

if given[1]%2 == 0:
    evens  += 1
else:
    odds += 1

if given[-1]%2 == 0:
    evens  += 1
else:
    odds += 1

if odds > evens:
    for i in given:
        if i%2==0:
            print(i)

else:
    for i in given:
        if not i%2==0:
            print(i)

Collapse
 
willsmart profile image
willsmart • Edited

A javascript one that has pretty reasonable complexity

function findOutlier(integers){
  // The first three ints can be used to determine whether we are 
  // looking for an odd or an even
  // If at least two are even, then we're looking for the odd integer
  const typicalIntegerIsEven = isEven(integers[0]) + isEven(integers[1]) + isEven(integers[2]) >= 2
  // Return the first integer that is non-typical
  return integers.find(v => isEven(v) != typicalIntegerIsEven)

  // Helper function to determine if a number is even or odd
  // Note that (-1)%2 === -1 and some integers might be negative.
  // (-2)%2 === -0 and -0 === 0, so this check will work for any integer.
  // v&1 is better in many ways, but only goes up to 32 bit ints
  function isEven(v) {return v%2 === 0}
}
Collapse
 
brightone profile image
Oleksii Filonenko

Elixir:

defmodule Outlier do
  require Integer

  def find(list) do
    if list
       |> Enum.take(3)
       |> Enum.filter(&Integer.is_even/1)
       |> Enum.count() == 1,
       do: Enum.find(list, &Integer.is_even/1),
       else: Enum.find(list, &Integer.is_odd/1)
  end
end
Collapse
 
jckr profile image
Jerome Cukier • Edited

in JavaScript. o(n), uses constant space.

in the worst case (outlier is at the end of the loop) it will go through all items. but if the outlier is found before, the loop stops.

function findOutlier(nums) {
  let lastOddOrEven = [null, null];
  for (let i = 0; i < nums.length; i++) {
    const parity = nums[i] % 2;
    if (lastOddOrEven[0] !== null && lastOddOrEven[1] !== null) {
      // we've already seen one odd and one even number,
      // so the outlier is the one number we've seen with a
      // different parity
      return lastOddOrEven[1 - parity];
    }
    lastOddOrEven[parity] = nums[i];
  }
  // if the loop can't return the outlier, this is because it's the last item
  return nums[nums.length - 1];
}
Collapse
 
tanguyandreani profile image
Tanguy Andreani • Edited

Bad solution! See comments below!

Ruby solution, I tried to do something different.

def findOutlier numbers
  sum = numbers.sum
  if sum.odd?
    numbers.find(&:odd?)
  else
    numbers.find(&:even?)
  end
end

puts findOutlier([2, 4, 0, 100, 4, 11, 2602, 36])
puts findOutlier([160, 3, 1719, 19, 11, 13, -21])
puts findOutlier([4, 8, 15, 16, 24, 42])
puts findOutlier([16, 6, 40, 66, 68, 28])
puts findOutlier([5, 9, 4, 155, 7])

When the list has no exception, the first element is returned; except when numbers looks like [3,3] (bug that you can fix by adding .uniq when computing the sum.)

Collapse
 
easyaspython profile image
Dane Hillard

I believe this would fail if the outlier is even and the rest are an odd number of odd numbers. The examples all have an even number of odd numbers. Can you check that?

Collapse
 
tanguyandreani profile image
Tanguy Andreani

It seems that I can’t make it right and as simple as it was. So I’ll stick with this solution:

def findOutlier numbers
  if numbers.first(3).count(&:even?) > 1
    numbers.find(&:odd?)
  else
    numbers.find(&:even?)
  end
end

puts findOutlier([2, 4, 0, 100, 4, 11, 2602, 36])
puts findOutlier([160, 3, 1719, 19, 11, 13, -21, 33])
puts findOutlier([160, 3, 1719, 19, 11, 13, -21])
puts findOutlier([4, 8, 15, 16, 24, 42])
puts findOutlier([16, 6, 40, 66, 68, 28])
puts findOutlier([3,3])
Collapse
 
matrossuch profile image
Mat-R-Such

Python

def find_outlier(integers):
    a= sum(map(int,[integers[0]%2,integers[1]%2,integers[2]%2]))
    if a == 0 or a== 1:
       for i in integers:
           if i % 2 == 1:   return i
    else:
        for i in integers:
            if i % 2 == 0:   return i
Collapse
 
oscherler profile image
Olivier “Ölbaum” Scherler

Erlang.

  • If the first two numbers have the same parity, I search the rest of the array for the other parity;
  • If they have different parities, I rotate them with the third number and check the resulting three-element array.
-module( outlier ).

-include_lib("eunit/include/eunit.hrl").

outlier( [ A, B, C | Rest ] ) ->
    case { abs( A rem 2 ), abs( B rem 2 ) } of
        { S, S } -> outlier( [ C | Rest ], 1 - S );
        { _, _ } -> outlier( [ B, C, A ] )
    end.
outlier( [ A | _ ], S ) when abs( A rem 2 ) == S ->
    A;
outlier( [ _ | Rest ], S ) ->
    outlier( Rest, S ).    

outlier_test_() -> [
    ?_assertEqual( 11, outlier( [ 2, 4, 0, 100, 4, 11, 2602, 36 ] ) ),
    ?_assertEqual( 160, outlier( [ 160, 3, 1719, 19, 11, 13, -21 ] ) ),
    ?_assertEqual( 15, outlier( [ 4, 8, 15, 16, 24, 42 ] ) ),

    ?_assertEqual( 2, outlier( [ 1, 2, 3, 5 ] ) ),
    ?_assertEqual( 1, outlier( [ 1, 2, 4, 6 ] ) ),
    ?_assertEqual( 2, outlier( [ 2, 1, 3, 5 ] ) ),
    ?_assertEqual( 1, outlier( [ 2, 1, 4, 6 ] ) ),

    ?_assertError( function_clause, outlier( [ 16, 6, 40, 66, 68, 28 ] ) ),
    ?_assertError( function_clause, outlier( [ 16, 6 ] ) )
].
Collapse
 
mrdulin profile image
official_dulin

Go:

func FindOutlier(integers []int) int {
  var m = map[string][]int{
    "odd": []int{},
    "even": []int{},
  }
  for _, i := range integers {
    if i % 2 == 0 {
      m["even"] = append(m["even"], i)
    } else {
      m["odd"] = append(m["odd"], i)
    }
  }
  if len(m["even"]) == 1 {
    return m["even"][0]
  } 
  return m["odd"][0]
}
Collapse
 
peter279k profile image
peter279k

Here is the simple solution with PHP:

function find($integers) {
  $evenArray = [];
  $oddArray = [];

  foreach ($integers as $integer) {
    if ($integer % 2 === 0) {
      $evenArray[] = $integer;
    } else {
      $oddArray[] = $integer;
    }
  }

  if (count($evenArray) === 1) {
    return $evenArray[0];
  }

  return $oddArray[0];
}
Collapse
 
muhammadhasham profile image
Muhammad Hasham

With JS

function findOutlier(arr){
let checker = {even:[],odd:[]}
arr.forEach((item) => item%2==0 ? checker['even'].push(item) : checker['odd'].push(item));
return checker['even'].length < checker['odd'].length ? checker['even'][0] : checker['odd'][0];
}

findOutlier([2, 4, 0, 100, 4, 11, 2602, 36])

Explanation:

  1. Using an object which stores even and odd numbers.
  2. just returning the one with less number.
Collapse
 
vanbliser profile image
Ayogu Blossom Israel

array = [500,502,1002,1234,601]
odd = even = i = 0
oddValue = evenValue = 0
a = len(array)
while (i < a):
if (array[i] % 2):
oddValue = array[i]
odd += 1
else:
evenValue = array[i]
even += 1
i += 1
if (odd > even == 1):
print(evenValue)
elif (odd == 1):
print(oddValue)
else:
print("Wrong list of numbers")

Collapse
 
asg5704 profile image
Alexander Garcia

Not elegant, but it'll do the job.

const findOutlier = (arr) => {
 const firstPass = arr.filter(el => el % 2 === 0)
 const secondPass = arr.filter(el => el % 2 !== 0)

 if(firstPass.length === 1) {
   return firstPass[0]
 }
 return secondPass[0]
}
Collapse
 
juliancanderson profile image
Julian Christian Anderson

This is the shortest solution I can create.

const isEven = n => n%2 === 0
const isOdd = n => n%2 > 0

const findOutlier = (arr) => {
  const evenArr = arr.filter(isEven)
  const oddArr = arr.filter(isOdd)

  return evenArr > oddArr ? oddArr[0] : evenArr[0]
}

console.log(findOutlier([2, 4, 0, 100, 4, 11, 2602, 36]))
console.log(findOutlier([160, 3, 1719, 19, 11, 13, -21]))
console.log(findOutlier([4, 8, 15, 16, 24, 42] ))
console.log(findOutlier([16, 6, 40, 66, 68, 28]))

Collapse
 
tazeg profile image
JeffProd
function findOutlier(integers){
  let oddCount = 0, evenCount = 0, r1 = 0, r2 = 0
  integers.forEach((i)=>{
   if(i % 2 == 0) {evenCount++; r1 = i;}
   else if(Math.abs(i % 2) == 1) {oddCount++; r2 = i;}
  })
  return (evenCount>oddCount)?r2:r1
}
Collapse
 
mfaghfoory profile image
Meysam Faghfouri • Edited
let findOutlier = (arr) => {
  const g1 = arr.filter(x => x % 2 === 0);
  const g2 = arr.filter(x => x % 2 !== 0);
  if(g1.length > g2.length )
    return g2[0];
  else
    return g1[0];
}
Collapse
 
hanachin profile image
Seiei Miyagi

ruby 2.7

def findOutlier(a) a.group_by(&:even?).each_value { return @1 if @2.nil? }; nil end
p [
  [2, 4, 0, 100, 4, 11, 2602, 36],
  [160, 3, 1719, 19, 11, 13, -21],
  [4, 8, 15, 16, 24, 42],
  [16, 6, 40, 66, 68, 28]
].map(&self.:findOutlier)

# [11, 160, 15, nil] 
Collapse
 
room_js profile image
JavaScript Room

Dart solution:

findOutlier(List nums) {
  var odds = new List();
  var evens = new List();
  nums.forEach((num) => num % 2 == 0 ? evens.add(num) : odds.add(num));

  if (odds.length == 0 || evens.length == 0) { return null; }

  return (odds.length < evens.length ? odds : evens)[0];
}

Link to the online playground: dartpad.dartlang.org/d5e83e228c72d...

Collapse
 
frncesc profile image
Francesc Busquets

This is my proposal:

function findOutlier(arr){
  const even=[], odd=[];
  arr.find(n => {
    (n%2 ? even : odd).push(n);
    return even.length ? odd.length > 1 : odd.length ? even.length > 1 : false;    
  });
  return even.length === 1 ? even[0] : odd.length === 1 ? odd[0] : null;
}

In this case, Array.find will stop looping when both the even and odd arrays have at least one item.

There is only one loop on the array values, and this loop stops just when the "strange element" is found.

At the end, the group with just one element has the solution.

In the last test, an array formed entirely by even numbers, null is returned.

Collapse
 
ra9 profile image
Carlos Nah • Edited

Here's my code:
I believe I could have used filters on the arrays method but just decided to follow the long step.



  const findOutlier = (arr) => {
    const evens = [];
    const odds = [];
    for(let i in arr) {
        const isEven = arr[i] % 2 === 0;
        const isOdd = !isEven;
        if(isEven){
            evens.push(arr[i]);
        }
        if(isOdd) {
            odds.push(arr[i])
        } 
    }

    if(odds.length === 0 || evens.length === 0) {
        return null;
    }

    return  odds.length  < evens.length ? odds[0] : evens[0];
  }

  console.log([
      [160, 3, 1719, 19, 11, 13, -21],
      [4, 8, 15, 16, 24, 42],
      [16, 6, 40, 66, 68, 28]
  ].map(findOutlier));

Here's my code:
I believe I could have used filters on the arrays method but just decided to follow the long step.



  const findOutlier = (arr) => {
    const evens = [];
    const odds = [];
    for(let i in arr) {
        const isEven = arr[i] % 2 === 0;
        const isOdd = !isEven;
        if(isEven){
            evens.push(arr[i]);
        }
        if(isOdd) {
            odds.push(arr[i])
        } 
    }

    if(odds.length === 0 || evens.length === 0) {
        return null;
    }

    return  odds.length  < evens.length ? odds[0] : evens[0];
  }

  console.log([
      [160, 3, 1719, 19, 11, 13, -21],
      [4, 8, 15, 16, 24, 42],
      [16, 6, 40, 66, 68, 28]
  ].map(findOutlier));

Here's my code:
I believe I could have used filters on the arrays method but just decided to follow the long step.



  const findOutlier = (arr) => {
    const evens = [];
    const odds = [];
    for(let i in arr) {
        const isEven = arr[i] % 2 === 0;
        const isOdd = !isEven;
        if(isEven){
            evens.push(arr[i]);
        }
        if(isOdd) {
            odds.push(arr[i])
        } 
    }

    if(odds.length === 0 || evens.length === 0) {
        return null;
    }

    return  odds.length  < evens.length ? odds[0] : evens[0];
  }

  console.log([
      [160, 3, 1719, 19, 11, 13, -21],
      [4, 8, 15, 16, 24, 42],
      [16, 6, 40, 66, 68, 28]
  ].map(findOutlier));

Collapse
 
hectorpascual profile image
Héctor Pascual

Python :

def find_outlier(array):
    odd = [i for i in array if i%2 == 0]
    even = [i for i in array if i%2]

    if not even or not odd:
        return "ERROR"
    elif len(even) > len(odd):
        return odd[0]
    else:
        return even[0]
Collapse
 
d3press3dd profile image
Anthony Rosman

this only iterates the array 3 times, and with that you can know if the number is even or odd and with the find it will only iterate until it finds it, when it finds it it will stop and so I will not have to iterate over the array in case it has 10000000000 elements and it is in a close position.

what do you guys think?

function findOutlier(integers){
  //your code here
  let isEven = 0;
  let isOdd = 0;
  let outlier;
  for (let i = 0; i < 3; i++) {
    if (Math.abs(integers[i]) % 2 === 0) {
      isEven += 1;
    } else {
      isOdd += 1;
    }
  }
  if (isEven < isOdd) {
   return integers.find(number => Math.abs(number) % 2 === 0);
  } else {
    return integers.find(number => Math.abs(number) % 2 !== 0);
  }  
}
Enter fullscreen mode Exit fullscreen mode
Collapse
 
vanbliser profile image
Ayogu Blossom Israel

array = [500,502,1002,1234,601]
odd = even = i = 0
oddValue = evenValue = 0
a = len(array)
while (i < a):
if (array[i] % 2):
oddValue = array[i]
odd += 1
else:
evenValue = array[i]
even += 1
i += 1
if (odd > even == 1):
print(evenValue)
elif (odd == 1):
print(oddValue)
else:
print("Wrong list of numbers")

Collapse
 
mwlang profile image
Michael Lang

Ruby Language

With specs!

def outlier values
  o = values.partition(&:odd?).sort_by(&:size)[0]
  o[0] if o.size == 1
end

require "spec"

describe "#name_shuffler" do
  it { expect(outlier [2, 4, 0, 100, 4, 11, 2602, 36]).to eq 11}
  it { expect(outlier [160, 3, 1719, 19, 11, 13, -21]).to eq 160}
  it { expect(outlier [4, 8, 15, 16, 24, 42]).to eq 15}
  it { expect(outlier [16, 6, 40, 66, 68, 28]).to eq nil}
end

output

>> rspec outlier.rb
....

Finished in 0.0052 seconds (files took 0.15152 seconds to load)
4 examples, 0 failures