The task Given an array of integers, find the one that appears an odd number of times.
There will always be only one integer that appears an odd number of times.
Examples [0,1,0,1,0] should return 0, because it occurs 3 times (which is odd). [1,2,2,3,3,3,4,3,3,3,2,2,1] should return 4, because it appears 1 time (which is odd).
I saw this solution but I struggle to understand the logic why it works:
e.g.
function findOdd(arr) {
return arr.find((item) => arr.filter(el => el == item).length % 2)
}
console.log(findOdd([20,1,-1,2,-2,3,3,5,5,1,2,4,20,4,-1,-2,5])) // returns 5
If the number must be odd, why it isn't ... .length % 2 !== 0;
I'd really appreciate any help! Thanks :)
arr.filter(el => el == item).length % 2 returns 0 or 1. This is good enough, as that value will be coerced to boolean, and since 0 is falsy and 1 truthy, it has the intended effect.
Note that this algorithm has a O(n²) complexity. It is possible to do this more efficiently.
function findOdd(arr) {
return arr.reduce((a, b) => a ^ b);
}
console.log(findOdd([20,1,-1,2,-2,3,3,5,5,1,2,4,20,4,-1,-2,5])) // returns 5This uses XOR. All values in the array are XOR'd together. It is based on the consideration that a ^ a == 0 for any value of a. And a ^ 0 == a. So if we have an odd number of a, we will get a, otherwise 0. As there is only one number whose occurrence is odd, we will find it this way. The special case of 0 will also work.
This is a quick and efficient solution
arr.find((item)=>{} this will loop through each items in the array and return the first satisfied value where we return true;
arr.filter(el => el == item) this will again loop through the same array and returns array of duplicate elements
example if arr = [1,1,2,1,3] then arr.filter(el => el == 1) will return [1,1,1];
arr.filter(el => el == item).length % 2 this will return the reminder of result array of duplicate elements divide by 2, which should be 0 or 1
For javascript 0 == false and 1 == true; so when the find loop found a 1 from filter it will return the value;