Find Missing Element

Given an integer set from 1 to n, calculate the missing integer.

by Hugh Chapman

HTML

<p>
Q: Given the following integer array beginning at 1 [<span id="Set"></span>] ; find the missing element
</p>
<p>
The missing element is <span id="Result"></span>.
</p>

JavaScript

var set = [2,3,4,5,6,7,8,9];
var result = document.querySelector('#Result');
document.querySelector('#Set').textContent = set.join(', ');

/* The Sum method has the potential of integer overflow if the sum exceed maximum integer value:
		1. Get the sum of numbers 
       total = n*(n+1)/2 // where n is length of the array
		2  Subtract all the numbers from sum and
  	 	 you will get the missing number.

   This is example of Sum Method:
   function findMissing (set)
		{
    		var i, n, total;
        n = set.length;
    		total  = (n+1)*(n+2)/2;   
    		for ( i = 0; i< n; i++ )
       		total -= set[i];
    		return total;
		}
*/

/* XOR method is a better solution */

function findMissing(set) {
	var x1 = set[0]; // XOR for elems in array
  var x2 = 1; // XOR for all the integers from 1 to n + 1
  
  for ( var i = 1; i < set.length; i++ ) {
        x1 = x1 ^ set[i];
  }
  
  for ( var i = 2; i <= set.length + 1; i++) {
        x2 = x2 ^ i;   // just counting up from 1 and doing XOR      
  }
  
  return (x1 ^ x2); // The difference in XOR (bitwise) is the missing value
}

document.querySelector('#Result').textContent = findMissing(set).toString();