how to find missing number in array

How to Find Missing Number in Array#

As a programmer, it is not uncommon to encounter an array that has a missing number. This could happen due to various reasons, such as human error or data corruption. Thankfully, there are multiple ways to find the missing number in an array.

Method 1: Using the Sum Formula#

One of the easiest ways to find the missing number in an array is to use the sum formula. This method involves finding the sum of all the elements in the array and comparing it with the expected sum of all the elements in the array (assuming that there are no missing numbers).

function findMissingNumber(array) {
  let n = array.length + 1;
  let expectedSum = (n * (n + 1)) / 2;
  let actualSum = array.reduce((acc, cur) => acc + cur);
  return expectedSum - actualSum;
}

// Example usage
let array = [1, 2, 3, 4, 6];
let missingNumber = findMissingNumber(array); // Returns 5

In this method, we first calculate the expected sum of all the elements in the array using the sum formula (n * (n + 1)) / 2, where n is the length of the array plus one (because there is a missing number). We then calculate the actual sum of all the elements in the array using the reduce method. Finally, we subtract the actual sum from the expected sum to get the missing number.

Method 2: Using the XOR Operator#

Another efficient way to find the missing number in an array is to use the XOR operator. This method involves XORing all the elements in the array and XORing the result with all the numbers from 1 to n (where n is the length of the array plus one).

function findMissingNumber(array) {
  let n = array.length + 1;
  let xorAll = array.reduce((acc, cur) => acc ^ cur);
  let xor1ToN = 1;
  for (let i = 2; i <= n; i++) {
    xor1ToN ^= i;
  }
  return xorAll ^ xor1ToN;
}

// Example usage
let array = [1, 2, 3, 4, 6];
let missingNumber = findMissingNumber(array); // Returns 5

In this method, we first use the reduce method to XOR all the elements in the array. We then XOR all the numbers from 1 to n using a for loop. Finally, we XOR the result of the two XOR operations to get the missing number.

Method 3: Using Binary Search#

If the array is sorted, we can also use binary search to find the missing number. This method involves dividing the array into two halves and checking which half contains the missing number.

function findMissingNumber(array) {
  let lo = 0;
  let hi = array.length - 1;
  while (lo <= hi) {
    let mid = Math.floor((lo + hi) / 2);
    if (array[mid] - mid !== array[0]) {
      hi = mid - 1;
    } else {
      lo = mid + 1;
    }
  }
  return array[lo] - 1;
}

// Example usage
let array = [1, 2, 3, 4, 6];
let missingNumber = findMissingNumber(array); // Returns 5

In this method, we first initialize the low and high indices to the first and last index of the array, respectively. We then use a while loop to divide the array into two halves until we find the missing number. In each iteration of the loop, we calculate the middle index using Math.floor((lo + hi) / 2) and check if the element at that index minus the index itself is equal to the first element of the array. If it is, then the missing number is in the second half of the array; otherwise, it is in the first half. We update the low or high index accordingly and repeat until we find the missing number.