#include <stdio.h>
/*
The essence of O(1) space complexity is that the algorithm uses a fixed amount of memory,
regardless of input size. Time complexity here is O(n) because we must scan the array.
*/
int findMissingNumber(const int arr[], int size) {
// formula for the sum of the first (size+1) natural numbers
long expected_sum = (long)(size + 1) * (size + 2) / 2;
long actual_sum = 0;
for (int i = 0; i < size; i++) {
actual_sum += arr[i];
}
return (int)(expected_sum - actual_sum);
}
int main(void) {
int arr[] = {1, 2, 4, 5, 6};
int size = sizeof(arr) / sizeof(arr[0]);
printf("Missing number: %d\n", findMissingNumber(arr, size));
return 0;
}
/*
run:
Missing number: 3
*/
