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 <stdio.h>
2
3int missingNumber(int* nums, int numsSize) {
4 int total = numsSize * (numsSize + 1) / 2;
5 int sum = 0;
6 for (int i = 0; i < numsSize; i++) {
7 sum += nums[i];
8 }
9 return total - sum;
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}The above C program calculates the sum of the array elements and subtracts it from the sum of numbers in the range [0, n], which is calculated using the formula n * (n + 1) / 2. This gives 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.