8
\$\begingroup\$

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?

\$\endgroup\$
13
\$\begingroup\$

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])
\$\endgroup\$
  • 3
    \$\begingroup\$ This is a lot better than the other solutions, because it only loops over the array once. \$\endgroup\$ – JAD Jul 10 at 7:04
  • \$\begingroup\$ This should be the accepted answer. Especially if it were a bit more readable, possibly with named functions for comparisons. \$\endgroup\$ – Eric Duminil Jul 10 at 7:23
  • 1
    \$\begingroup\$ One minor nitpick: In your ternary operator, you could avoid the double negation by using a[0] == a[1] and reversing the two statements : return a.find(a[0] == a[1] ? (v, i, a) => v != a[0] : (v, i, a) => v != a[2]); \$\endgroup\$ – Eric Duminil Jul 10 at 9:50
5
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ clever, but fails on [17, 3, 17, 17, 17, 17, 17, 17] (it returns 18) \$\endgroup\$ – Brandon Jul 10 at 18:19
  • 1
    \$\begingroup\$ @Brandon "You are given an odd-length array of integers, ..." \$\endgroup\$ – Théophile Jul 10 at 19:10
  • 1
    \$\begingroup\$ @AlexanderLomia But his array has an even number of elements! The ordering doesn't matter since XOR is commutative. The reason his example returns 18 is that there's an extra 17 left over, and 17 ^ 3 = 18. \$\endgroup\$ – Théophile Jul 10 at 19:23
  • \$\begingroup\$ @Théophile Yes, you're completely right! That example got me really confused, because I assumed that the array had an odd number of elements. Thanks for pointing that out! \$\endgroup\$ – Alexander Lomia Jul 10 at 19:37
  • \$\begingroup\$ Yeah good point \$\endgroup\$ – Brandon Jul 10 at 21:20
4
\$\begingroup\$

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;
\$\endgroup\$
  • \$\begingroup\$ Chrome really blew it here. In Firefox the "optimized" version is about 20% faster for me, as expected. Maybe worth reporting this on Chromium issue tracker, if it's not there already? +1 for going the extra mile. \$\endgroup\$ – user11536834 Jul 10 at 13:35
  • \$\begingroup\$ @EricDuminil See comment by said user above yours. that bit of code is why I posted as on chrome it was 20 times slower. Details in my answer. \$\endgroup\$ – Blindman67 Jul 10 at 19:08
  • \$\begingroup\$ @Blindman67: Sorry about that, I thought it was the second version. \$\endgroup\$ – Eric Duminil Jul 10 at 19:18
  • \$\begingroup\$ For FuncB you should really cache nums.length-1 if you want a fairer comparison \$\endgroup\$ – konijn Jul 12 at 19:36
  • \$\begingroup\$ @konijn caching length would only help for run once never again function as the optimizer will spot that the value is constant. My performance testing code pre runs the code allowing the optimizer to do its thing. Testing num.length - 1 against cached length results with a consistently slower performance (~40µs per call for same test as in answer (though this is below error rate and I would normally call it no difference)) This is likely due to the need to create the addition constant const len = nums.length - 1; on the heap each call \$\endgroup\$ – Blindman67 Jul 12 at 20:44
2
\$\begingroup\$

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...

\$\endgroup\$
1
\$\begingroup\$

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]));

\$\endgroup\$
  • 1
    \$\begingroup\$ Your filter code is O(n**2) while OP's code is O(n.log n), right? \$\endgroup\$ – Eric Duminil Jul 10 at 7:16
  • \$\begingroup\$ Indeed, the performance is horrible compared to this answer (see measurethat.net/Benchmarks/Show/5561/0/find-the-stray-v2) \$\endgroup\$ – Eric Duminil Jul 10 at 9:54
  • \$\begingroup\$ @Eric I completely agree that my solution is not the most efficient. Nor was it meant to be. Perhaps, and this is just me spit-balling here, there is more to coding than speed? Perhaps readability and maintainability have some value? Unless you're running this in a tight loop 36 thousand times a second, the performance difference will be negligible. \$\endgroup\$ – Heretic Monkey Jul 10 at 12:02
  • \$\begingroup\$ Thanks for the comment. Sorry if my words were a bit harsh. I totally agree that readability and maintainability are very important. I don't think the O(n) answer is less readable than yours, so it should be preferred IMHO. \$\endgroup\$ – Eric Duminil Jul 10 at 12:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.