How to useXOR in Javascript
Another efficient way to find the missing number is by using the XOR bitwise operation. This method takes advantage of the properties of XOR, which is both associative and commutative. XORing two identical numbers results in 0, and XORing a number with 0 results in the number itself.
Example:
function findMissingNumber(arr) {
const n = arr.length + 1;
// Step 1: Calculate XOR of all numbers from 1 to N
let xor_all = 0;
for (let i = 1; i <= n; i++) {
xor_all ^= i;
}
// Step 2: Calculate XOR of all elements in the array
let xor_arr = 0;
for (let i = 0; i < arr.length; i++) {
xor_arr ^= arr[i];
}
// Step 3: XOR of xor_all and xor_arr gives the missing number
const missingNumber = xor_all ^ xor_arr;
return missingNumber;
}
// Test case
const arr = [1, 2, 3, 5];
const missingNumber = findMissingNumber(arr);
console.log("Missing Number: ", missingNumber);
const arr2 = [1, 4, 3, 2, 6, 5, 7, 10, 9];
const missingNumber2 = findMissingNumber(arr2);
console.log("Missing Number: ", missingNumber2);
Output
Missing Number: 4 Missing Number: 8
JavaScript Program to Find the Missing Number
Given an array of size N-1 with integers in the range of [1, N]. The task is to find the missing number from the first N integers. There are no duplicate elements allowed in the array.
Examples:
Input : arr = [1, 2, 3, 5]
Output : 4
Input : arr = [1, 4, 3, 2, 6, 5, 7, 10, 9]
Output : 8