**webdev**

Continuing with the series on JavaScript interview questions, here is Question 4: Given an array of non-negative integers, a second array is created by shuffling the first array and removing one integer. Find the missing integer.

As Arden discusses in his post, the brute force solution is super-simple: for every element in the second array, check to see if it exists in the first array.

Arden notes that this is highly inefficient, with a complexity of O(N^2). JavaScript doesn't give us any advantages here.

Arden also suggests a slightly more efficient solution can be had by sorting the arrays and comparing them one off. Since most sorting algorithms have a complexity of O(NlogN) that would be the most expensive part of that solution:

Here is the optimized solution that Arden suggests, using XOR (you can read the details on his post, it's really very clever and I don't think I would have ever thought of this solution myself).

Finally, there is a JavaScript specific solution that utilizes Array.indexOf:

This technique has a complexity of O(N), on par with Arden's clever solution.

As Arden discusses in his post, the brute force solution is super-simple: for every element in the second array, check to see if it exists in the first array.

function bruteForce(arr1, arr2) { var i = 0, j = 0, arr1Length = arr1.length, arr2Length = arr2.length, returnVal = -1; for (i = 0; i < arr1Length; i++) { var currTest = arr1[i], boolFound = false; for (j = 0; j < arr2Length; j++) { if (currTest === arr2[j]) { boolFound = true; } } if (boolFound === false) { returnVal = arr1[i]; } } return returnVal; }

Arden notes that this is highly inefficient, with a complexity of O(N^2). JavaScript doesn't give us any advantages here.

Arden also suggests a slightly more efficient solution can be had by sorting the arrays and comparing them one off. Since most sorting algorithms have a complexity of O(NlogN) that would be the most expensive part of that solution:

function betterMethod(arr1, arr2) { var i = 0, arr1Length = arr1.length, arr2Length = arr2.length, returnVal = -1; arr1.sort(); arr2.sort(); for (i = 0; i < arr1Length; i++) { var test1 = arr1[i], test2 = arr2[i]; if (test1 !== test2) { returnVal = test1; i = arr1Length; } } return returnVal; }

Here is the optimized solution that Arden suggests, using XOR (you can read the details on his post, it's really very clever and I don't think I would have ever thought of this solution myself).

function optimalMethod(arr1, arr2) { var i = 0, totArray = [], totArrayLength = arr1.length + arr2.length, returnVal = 0; totArray = totArray.concat(arr1, arr2); for (i = 0; i < totArrayLength; i++) { returnVal ^= totArray[i]; } return returnVal; }

Finally, there is a JavaScript specific solution that utilizes Array.indexOf:

function javaScriptSpecific(arr1, arr2) { var i = 0, arr1Length = arr1.length, returnVal = -1; for (i = 0; i < arr1Length; i++) { if (arr2.indexOf(arr1[i]) < 0) { returnVal = arr1[i]; } } return returnVal; }

This technique has a complexity of O(N), on par with Arden's clever solution.