find any duplicate element in array using javascript

Question

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

Input: [2,2,1]
Output: 1
Example 2:

Input: [4,1,2,1,2]
Output: 4

I found one solution

Bit Manipulation Concept

If we take XOR of zero and some bit, it will return that bit
a \oplus 0 = aa⊕0=a
If we take XOR of two same bits, it will return 0
a \oplus a = 0a⊕a=0
a \oplus b \oplus a = (a \oplus a) \oplus b = 0 \oplus b = ba⊕b⊕a=(a⊕a)⊕b=0⊕b=b
So we can XOR all bits together to find the unique number.

i tried to implement same approach in javascript like this

var singleNumber = function(nums) {
    let a = 0
    nums.forEach((i)=>{
        console.log(  a^=i)
        console.log(  a)
        a^=i;
    })

    return a
};

console.log(singleNumber([2,2,1]))

but it is not giving correct solution

Just a note: I would try to be consistent in my code. E.g. no semicolons at the end of all lines. Or function singleNumber(nums) instead of old style. — maraca
– maraca, Commented Mar 25, 2020 at 1:44
The caveat is that one number must appear exactly once and all other numbers, if any, exactly twice. Anything else and the result is meaningless (to me at least). :-) — RobG
– RobG, Commented Mar 25, 2020 at 2:37

CertainPerformance · Accepted Answer · 2020-03-25 01:48:22Z

1

You're doing a^=i twice on every iteration:

nums.forEach((i)=>{
    console.log(  a^=i)
    console.log(  a)
    a^=i;
})

As a result, a's bits get switched once, then they get switched back, so the result is always 0.

Remove the first console.log( a^=i), and it'll work:

var singleNumber = function(nums) {
    let a = 0
    nums.forEach((i)=>{
        a^=i;
    })

    return a
};

console.log(singleNumber([2,2,1]))

More concisely, with reduce:

const singleNumber = nums => nums.reduce((a, num) => a ^ num, 0);
console.log(singleNumber([2,2,1]))

If you want to log the result of the ^, use a ^ i:

var singleNumber = function(nums) {
    let a = 0
    nums.forEach((i)=>{
        console.log('a will become:', a ^ i);
        a^=i;
    })

    return a
};

console.log(singleNumber([2,2,1]))

edited Mar 25, 2020 at 1:48

answered Mar 25, 2020 at 1:40

CertainPerformance

373k55 gold badges354 silver badges359 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

user12130378 Over a year ago

Thanks for answering ..!! but still it not giving duplicate item

CertainPerformance Over a year ago

The goal is to return the non-duplicate item, not the duplicate item. Given a non-empty array of integers, every element appears twice except for one. Find that single one. So the desired output should be 1, and it is, right?

user12130378 Over a year ago

great anwser ...:)

Anthony McGrath · Accepted Answer · 2020-03-25 01:53:08Z

0

I think this uses linear runtime complexity, but uses an extra array which uses memory.

var f = function(input){
    var input2 = [];
    for (var i = 0 ; i < input.length; i++){
        if (input2[input[i]])
            input2[input[i]] += 1;
        else
            input2[input[i]] = 1;
    }

    for (var i = 0; i < input2.length; i++){
        if (input2[i] == 1)
            return i;
    }

    return input[0];
}

answered Mar 25, 2020 at 1:53

Anthony McGrath

8026 silver badges7 bronze badges

Collectives™ on Stack Overflow

find any duplicate element in array using javascript

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related