// 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 class MissingNumberFinder {
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);
}
public static void main(String[] args) {
int[] arr = {1, 2, 4, 5, 6};
int missing = findMissingNumber(arr);
System.out.println("Missing number: " + missing);
}
}
/*
run:
Missing number: 3
*/
