Question

How to find the missing number in an array containing numbers from 1 to n in O(1) time complexity with Pascal

Answer 1

program 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.
}

function FindMissingNumber(arr: array of Integer; size: Integer): Integer;
var
  expected_sum, actual_sum: LongInt;
  i: Integer;
begin
  { formula for sum of first (size+1) natural numbers }
  expected_sum := (size + 1) * (size + 2) div 2;
  actual_sum := 0;

  for i := 0 to size - 1 do
    actual_sum := actual_sum + arr[i];

  FindMissingNumber := expected_sum - actual_sum;
end;

var
  arr: array[0..4] of Integer = (1, 2, 4, 5, 6);
  size, missing: Integer;
begin
  size := Length(arr);
  missing := FindMissingNumber(arr, size);

  WriteLn('Missing number: ', missing);
end.



(*
run:

Missing number: 3

*)

 

70+ SQL courses for beginners and professionals