/*
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.
*/
function findMissingNumber(arr: number[]): number {
const size: number = arr.length;
// formula for the sum of the first (size+1) natural numbers
const expectedSum: number = (size + 1) * (size + 2) / 2;
let actualSum: number = 0;
for (let i: number = 0; i < size; i++) {
actualSum += arr[i];
}
return expectedSum - actualSum;
}
function main(): void {
const arr: number[] = [1, 2, 4, 5, 6];
const missing: number = findMissingNumber(arr);
console.log("Missing number:", missing);
}
main();
/*
run:
"Missing number:", 3
*/
