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.
1#include <iostream>
2#include <vector>
3using namespace std;
4
5int missingNumber(vector<int>& nums) {
6 int n = nums.size();
7 int total = n * (n + 1) / 2;
8 int sum = 0;
9 for (int num : nums) {
10 sum += num;
11 }
12 return total - sum;
13}
14
15int main() {
16 vector<int> nums = {3, 0, 1};
17 cout << "Missing number: " << missingNumber(nums) << endl;
18 return 0;
19}This C++ solution uses the same logic as the C solution. It iterates over the vector, sums up the elements, and subtracts this sum from the expected total sum 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.
1function missingNumber(nums) {
2 let xorResult = 0;
3 for (let i = 0; i < nums.length; i++) {
4 xorResult ^= i ^ nums[i];
5 }
6 return xorResult ^ nums.length;
7}
8
9// Usage
10const nums = [3, 0, 1];
11console.log("Missing number:", missingNumber(nums));This JavaScript solution applies XOR logic to efficiently compute the missing number from the sequence by exploiting cancellation properties.