loading...

re: The Gauss Sum, and Solving for the Missing Number VIEW POST

FULL DISCUSSION
 

I have seen problems like these solved more elegantly with XOR. If the numbers are very large, and the array is very long, you will run out of memory to hold your sum value. With XOR approach, the "counter" is only ever as large as the biggest number in the input array, regardless of array length.

The foundations of XOR approach are:

  1. any number, when XOR with itself, yields 0.
  2. any number, when XOR with 0, yields itself.

So in the example above, we have input [4, 1, 0, 2, 5].
If we create a second array of [0, 1, 2, 3, 4, 5] and XOR everything together, we will have

4 xor 1 xor 0 xor 2 xor 5 xor 0 xor 1 xor 2 xor 3 xor 4 xor 5

which is equal to

(0 xor 0) xor (1 xor 1) xor (2 xor 2) xor 3 xor (4 xor 4) xor (5 xor 5)

which is equal to 3. That's the missing number.

In fact we do not need to create the second array of [0, 1, 2, 3, 4, 5] either because that's just consecutive numbers, we can get it easily by using a single counter variable, or just use index of the input array (which goes naturally 0, 1, 2, 3, 4, etc.).

Solution would look something like this

function missingNumber(nums) {
  return nums.reduce((accumulatedResult, currentNumber, currentIndex) => {
    return accumulatedResult ^ currentNumber ^ (currentIndex +1 )
  }, 0)
}
code of conduct - report abuse