Find The One Element In An Array That is Different From The Others

Question

https://www.codewars.com/kata/find-the-stray-number/train/javascript

I solved this challenge by sorting from least to greatest, and checking if the first element in the array matched the second element in the array.

If the first element does not match, then the different element is the first element.

If the first element does match, then the different element is the last element.

function stray(numbers) {
  numbers = numbers.sort((a, b) => a - b);
  if (numbers[0] !== numbers[1]) {
    return numbers[0];
  }
  else {
    return numbers[numbers.length - 1];
  }
}
console.log(stray([17, 17, 3, 17, 17, 17, 17]));

I'm wondering if / how this can be done with the filter() method instead?

Answer 1

This is a similar idea to the other answers here, but the implementation is a bit different.

First of all, we can assume that the array's length is at least 3, since it needs to have at least two of the same values and one different value.

Let's start by handling the case where the stray value is not in the first element. We could simply write:

a.find(v => v != a[0])

That is, find an element that's different from the first element. But what if the stray element comes first in the array? We can check if the first two elements differ. If they do, then the stray is either in the first or second position, so the third element is not a stray. In this case, we can check against the third element instead of the first; otherwise we check against the first element as before, thus:

a.find(v => a[0] != a[1] ? v != a[2] : v != a[0])

This is a bit code-golfey and not very readable, so I wouldn't recommend it in production, but it may be of some interest as a curiosity.

It may be worth noting that this solution appears to perform quite well, and can be further optimized by doing the inequality check on the first two elements before invoking find, and by using the third parameter to find to access the array, making the callback a pure function and eliminating the need to reference the array via the closed-over variable, for example:

a.find(a[0] != a[1] ?
    (v, i, a) => v != a[2] :
    (v, i, a) => v != a[0])

Answer 2

I'll try to offer an alternative solution to your problem.

The linked kata contains the following piece of information

You are given an odd-length array of integers, in which all of them are the same, except for one single number

This means, that the array is guaranteed to contain even number of same elements.

This fact could be leveraged to achieve a very elegant solution using the XOR operator:

const arr = [17, 17, 3, 17, 17, 17, 17];

// XOR together every value inside arr
const answer = arr.reduce((acc, value) => acc ^= value, 0);

console.log(answer);

The complexity of this algorithm is O(n), as opposed to using sort, which runs in O(nlogn) at best (in most cases).

Now, the reason this works is that XOR operator has a useful property of "cancelling out" the same elements. In other words:

1. n ^ n = 0
2. n ^ 0 = x

Answer 3

There are some improvements that can be made to the already given answers. Especially as user11536834 second example was a surprisingly poor performer.

The following function improves upon given answers in terms of performance doing the same operation in 1/3rd the time

function find(nums) {
    const a = nums[0], b = nums[2];
    return a !== nums[1] ? 
        nums.find(v => v !== b):
        nums.find(v => v !== a);
}

Func A

If we consider he best solution so far

function findA(nums) {
    return nums.find(v => nums[0] != nums[1] ? v != nums[2] : v != nums[0])
}

We can double the performance by avoiding the cost of the call stack for each iteration by using a standard loop. This halves the processing time.

Func B

function findB(nums) {
    var i = 0, val = nums[i++];
    while (i < nums.length - 1) {
        if (nums[i++] !== val) {
            return val !== nums[i] ? val : nums[i - 1];
        }
    }
    return nums[i];
}

Modifying user11536834 second solution gave a very surprising result being 20 times slower than func A

Func C

function findC(nums) {
    return nums.find(nums[0] !== nums[1] ? v => v !== nums[2] : v => v !== nums[0])
}

OMDG that is 20 times slower than the first version. The optimizer obviously does not like the function declarations being conditional. So I moved the functions out of the ternary and added some other minor optimizations to get...

Func D

function findD(nums = data[(d++) % len]) {
    const a = nums[0], b = nums[2];
    return a !== nums[1] ? 
        nums.find(v => v !== b):
        nums.find(v => v !== a);
}

Now we are talking, it doubled the performance again by nearly 2 on the while loop version.

Performance comparison

Running a comparison performance benchmark on 2000 different arrays with random position of the odd number out and each array 2000 items long. The results as follows.

findA.:      4.239   ±1.723µs OPS 235,919   35% Total  1,170ms 276,000 operations
findB.:      2.225   ±1.172µs OPS 449,504   67% Total    714ms 321,000 operations
findC.:     38.612  ±10.163µs OPS  25,898    4% Total 11,120ms 288,000 operations
findD.:      1.496   ±0.725µs OPS 668,321 *100% Total    471ms 315,000 operations
OPS is Operations per second (Operation is the function being called)
µs is 1 / 1,000,000 second
ms is 1 / 1,000 second
*Best time is 100% of its self

Note that Javascript is seldom linear and that the length of the arrays tested was tested to be greater than the point where all 4 function were giving a linear result as the array size grew.

As tested

The test where conducted on the modified functions as follows. Data was created with 2 util functions listed below the next snippet.

var a = 0, b = 0, c = 0, d = 0;
const len = 2000;
const data = $setOf(len, i => {var b = $setOf(len, k => i); b[$randI(len)] = i + 1; return b});

// test name findA
function findA(nums = data[(a++) % len]) {
    return nums.find(v => nums[0] != nums[1] ? v != nums[2] : v != nums[0])
}

// test name findB
function findB(nums = data[(b++) % len]) {
    var i = 0, val = nums[i++];
    while (i < nums.length - 1) {
        if (nums[i++] !== val) {
            return val !== nums[i] ? val : nums[i - 1];
        }
    }
    return nums[i];
}

// test name findC
function findC(nums = data[(c++) % len]) {
    return nums.find(nums[0] !== nums[1] ? v => v !== nums[2] : v => v !== nums[0])
}

// test name findD
function findD(nums = data[(d++) % len]) {
    const a = nums[0], b = nums[2];
    return a !== nums[1] ? 
        nums.find(v => v !== b):
        nums.find(v => v !== a);
}

Utils

const $setOf = (count, fn = (i)=>i) => {var a = [],i = 0; while (i < count) { a.push(fn(i ++)) } return a };
const $randI = (min = 2, max = min + (min = 0)) => (Math.random() * (max - min) + min) | 0;

Answer 4

Here is how you could implement it with the filter() method:

const stray = numbers => +numbers.sort((a, b) => a - b)
  .filter((n,i,a) => (i === 0 && a[0] !==a[1]) || (i === a.length-1 && a[a.length-1] !== a[a.length-2]));

console.log(stray([17, 17, 3, 17, 17, 17, 17]));
console.log(stray([2, 2, 2, 2, 2, 14, 2, 2, 2, 2]));

Or in more a clean way:

const stray = numbers => numbers.sort((a, b) => a - b)
  .filter(n => n === numbers[0]).length === 1 ? numbers[0] : numbers[numbers.length-1]

console.log(stray([17, 17, 3, 17, 17, 17, 17]));
console.log(stray([2, 2, 2, 2, 2, 14, 2, 2, 2, 2]));

But as Heretic Monkey said, this is probably not the best approach...

Answer 5

You could use the filter method, but I'm not convinced it makes the code any more efficient or readable:

function stray(numbers) {
  return numbers.find(i => numbers.filter(j => j === i).length === 1);
}
console.log(stray([17, 17, 3, 17, 17, 17, 17]));
console.log(stray([17, 17, 23, 17, 17, 17, 17]));

^{I've added an example where the "stray" number is greater than the others as a sanity check.}

find is a bit like filter except that it returns the first element in the array that causes the function to return true.

filter here is used to find the number which is only found in the array once.

---

Your original code could be shortened by using a conditional operator, along with the slice function (which shortens the code necessary to get the first/last element a little):

function stray(numbers) {
  numbers = numbers.sort((a, b) => a - b);
  return numbers.slice((numbers[0] !== numbers[1] ? 0 : -1))[0];
}
console.log(stray([17, 17, 3, 17, 17, 17, 17]));
console.log(stray([17, 17, 23, 17, 17, 17, 17]));