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