JS: Finding unpaired elements in an array

Question

I have the following question (this is not school -- just code site practice questions) and I can't see what my solution is missing.

A non-empty array A consisting of N integers is given. The array contains an odd number of elements, and each element of the array can be paired with another element that has the same value, except for one element that is left unpaired.

Assume that:

*N is an odd integer within the range [1..1,000,000];
*each element of array A is an integer within the range [1..1,000,000,000];
*all but one of the values in A occur an even number of times.

EX: A = [9,3,9,3,9,7,9] Result: 7

The official solution is using the bitwise XOR operator :

function solution(A) {
    
    var agg = 0;
    
    for(var i=0; i<A.length; i++) {
        agg ^= A[i];
    }
    
    return agg;
}

My first instinct was to keep track of the occurrences of each value in a Map lookup table and returning the key whose only value appeared once.

function solution(A) {

    if (A.length < 1) {return 0}
    let map = new Map();
    let res = A[0]
    for (var x = 0; x < A.length; x++) {
        if (map.has(A[x])) {
            map.set(A[x], map.get(A[x]) + 1)
        } else {
            map.set(A[x], 1)
        }
    }
    for ([key,value] of map.entries()) {
        if (value===1) {
            res = key
        } 
    }

    return res;
}

I feel like I handled any edge cases but I'm still failing some tests and it's coming back with a 66% correct by the automated scorer.

I think the example is wrong... it should be `[9,3,9,7,3] => 7` — We Are All Monica, Aug 21 '18 at 06:54
@Bergi It's not super descriptive: *small random test n=201 ✘WRONG ANSWER got 91 expected 42* . and *big random test n=999,999, multiple repetitions ✘WRONG ANSWER got 330 expected 700* — Jason Boyas, Aug 21 '18 at 06:55

score 11 · Answer 1 · answered Aug 21 '18 at 07:01

11

You could use a Set and check if deletion deletes an item or not. If not, then add the value to the set.

function check(array) {
    var s = new Set;
    
    array.forEach(v => s.delete(v) || s.add(v));
    
    return s.values().next().value;
}

console.log(check([9, 3, 9, 7, 3, 9, 9])); // 7

answered Aug 21 '18 at 07:01

Nina Scholz

376,160
25
347
392

ah , this is rather clever. I didn't think of that, thank you! – Jason Boyas Aug 21 '18 at 07:09
This is a great approach Nina. I don't know much about Set's this made me look a bit more into it. – rodcunha May 29 '19 at 21:30

score 4 · Accepted Answer · answered Aug 21 '18 at 06:52

4

You're not accounting for cases like this:

[ 1, 1, 2, 2, 2 ] => the last 2 is left unpaired

So your condition should be if ( value % 2 ) instead of if ( value === 1 ).

I think also there is not much benefit to using a Map rather than just a plain object.

answered Aug 21 '18 at 06:52

We Are All Monica

13,000
8
46
72

so changing it to that passed 100% of the cases, thanks! Can you explain why I'm using the modulo operator here? – Jason Boyas Aug 21 '18 at 07:01
If a given element appears 2, 4, 6, 8... times, then all of them can be paired. – We Are All Monica Aug 21 '18 at 07:10
If it appears 1, 3, 5, 7... times, then there is one left over, unpaired. You want to test whether the number of times an element appears is divisible by 2. – We Are All Monica Aug 21 '18 at 07:10

score 1 · Answer 3 · answered Aug 11 '20 at 18:42

The official solution works due to the properties of the bitwise XOR (^), namely the fact that a ^ a == 0, a ^ 0 == a, and that the operation is commutative and associative. This means that any two equal elements in the array will cancel each other out to become zero, so all numbers appearing an even amount of times will be removed and only the number with an odd frequency will remain. The solution can be simplified using Array#reduce.

function findOdd(arr) {
    return arr.reduce((a,c)=>a ^ c, 0);
}

Koushik Chatterjee · Answer 4 · 2018-08-23T09:31:04.043

You need not to make a count of each and traverse again, if you are sure that there will be exactly one number which will occur odd number of times. you can sum the array and do + when odd entry and - when even entry (to dismiss it back) and in the hash (map or object) you can just toggle for subsequent entry of each number.

Here is an example:

let inputArray1 = [10,20,30,10,50,20,20,70,20,70,50, 30,50], //50 -> 3 times
    inputArray2 = [10,20,30,20,10], //30 -> 1 time
    inputArray3 = [7,7,7,7,3,2,7,2,3,5,7]; //5 -> 1 time

let getOddOccuence = arr => {
  let hash = {};
  return arr.reduce((sum, n) => sum + ((hash[n] = !hash[n]) ? n : -n), 0);
}

console.log('Input Array 1: ', getOddOccuence(inputArray1));
console.log('Input Array 2: ', getOddOccuence(inputArray2));
console.log('Input Array 3: ', getOddOccuence(inputArray3));

In case the input contains multiple or no numbers having odd number of occurance (if you are not sure there) then you have already the hash (and you can ignore performing sum) and return the keys of hash (where value is true (and not checking with %2 and then consider as truthy or false in case of you have count))

score 0 · Answer 5 · answered Jan 15 '19 at 16:49

function solution(A) {
    let result = 0;
  
    for (let element of A) {
        // Apply Bitwise XOR to the current and next element
        result ^= element;
    }

    return result;
}

const unpaired = solution([9, 3, 9, 3, 9, 7, 9]);

console.log(unpaired);

Source: https://gist.github.com/k0ff33/3eb60cfb976dee0a0a969fc9f84ae145

JS: Finding unpaired elements in an array

5 Answers5