Outliers

Oh boy, this one involved some thinking. The problem is to find the outlier in an array of integers. You are given a list that has a minimum of three elements but can have up to a thousand. The array will always have either all even numbers and exactly one odd number or all odd numbers and exactly one even number.

The task is to find the outlier.

Example

  • [1,2,3,5,7,9] the outlier is 2
  • [-1, 0,1,65,37] the outlier is 0

I did not come up with two different approaches today, just the one but let’s take a close look at that one.

The Outlier Code

function findOutlier(integers) {
    const sum = Math.abs(integers[0] % 2) + Math.abs(integers[1] % 2) + Math.abs(integers[2] % 2)
    const isEven = sum <= 1
    return integers.find(num => {
        return isEven ? num % 2 !== 0 : num % 2 === 0
    })
}
Code language: JavaScript (javascript)

The most complicated part is line 2. We know that our list will have at least 3 elements so we can use those elements to determine if the rest of our list is even or odd.

We also know that there will be exactly one outlier but we do not know if it is at the beginning, in the middle, or at the end of the list.

Our first point of action is to use the first 3 elements to determine if we have an even list or an odd list. But this is complicated by the possibility of the outlier being part of the first 3 elements. So the first line simplifies those first 3 elements into either 0 or 1. We use the Math.abs function because negative integers are a thing.

We sum up the 3 numbers and our possible values will look like the table below

First NumberSecond numberThird NumberSum
even, even, even0000
even, even, odd0011
odd, odd, even1102
odd, odd, odd1113

The order is irrelevant since (even, even, odd) will give the same result as (even, odd, even), because associative law. Looks like that Maths degree won’t be a total loss.

So if our sum is 0 or 1 we have an even list and are looking for an odd outlier and if it’s 2 or 3 we have an odd list looking for an even outlier.

The rest is child play.

I didn’t really have a lot of time to look for a second approach so I’ll leave it at one today. But If you have a different approach I’d love to see it. Ping me on Twitter @phoexer and as always happy coding.