This approach uses the formula for the sum of the first n natural numbers: Sum = n * (n + 1) / 2. By calculating the sum of the numbers from the array and subtracting it from the expected sum, we can find the missing number.
Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(1), as no additional space is used beyond variables.
1function missingNumber(nums) {
2 const n = nums.length;
3 const total = n * (n + 1) / 2;
4 const sum = nums.reduce((acc, val) => acc + val, 0);
5 return total - sum;
6}
7
8// Usage
9const nums = [3, 0, 1];
10console.log("Missing number:", missingNumber(nums));This JavaScript solution uses the reduce() method to compute the sum of the array's elements and applies the arithmetic formula to find the missing number.
An efficient approach is using XOR. XORing a number with itself results in zero (n ^ n = 0), and XOR of any number with zero keeps the number unchanged (n ^ 0 = n). By XORing all indices and array elements together, each number present in both will cancel out, leaving the missing number.
Time Complexity: O(n), iterating through the array.
Space Complexity: O(1), using constant space.
1#include <stdio.h>
2
3int missingNumber(int* nums, int numsSize) {
4 int xor_result = 0;
5 for (int i = 0; i < numsSize; i++) {
6 xor_result ^= i ^ nums[i];
7 }
8 xor_result ^= numsSize;
9 return xor_result;
10}
11
12int main() {
13 int nums[] = {3, 0, 1};
14 int missing = missingNumber(nums, 3);
15 printf("Missing number: %d\n", missing);
16 return 0;
17}This C solution utilizes XOR properties: iterates through the array, XORing indices and elements to find the single non-repeated element, which is the missing number.