using System;
class MissingNumberFinder
{
/*
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.
*/
public static int FindMissingNumber(int[] arr) {
int size = arr.Length;
// formula for the sum of the first (size+1) natural numbers
long expectedSum = (long)(size + 1) * (size + 2) / 2;
long actualSum = 0;
for (int i = 0; i < size; i++) {
actualSum += arr[i];
}
return (int)(expectedSum - actualSum);
}
static void Main()
{
int[] arr = { 1, 2, 4, 5, 6 };
int missing = FindMissingNumber(arr);
Console.WriteLine("Missing number: " + missing);
}
}
/*
run:
Missing number: 3
*/
