program MinimalTwoSum;
{$mode objfpc}{$H+}
{
Goal:
-----
Find the minimal value of (a[i] + a[j]) for any two distinct elements in an array.
Efficient Strategy (O(n)):
--------------------------
The smallest possible sum of two distinct elements is obtained by:
- finding the smallest element
- finding the second smallest element
Because any other pair must be >= one of these two.
We scan the array once, keeping track of:
- min1 = smallest element seen so far
- min2 = second smallest element seen so far
}
uses
SysUtils;
// A function that computes the minimal sum of two distinct elements.
function MinimalTwoSum(const arr: array of Integer): Integer;
var
min1, min2, x: Integer;
i: Integer;
begin
// Handle edge case: need at least two elements
if Length(arr) < 2 then
begin
raise Exception.Create('Array must contain at least two elements.');
end;
// Initialize min1 and min2 to very large values
min1 := High(Integer);
min2 := High(Integer);
// Single pass through the array
for i := 0 to High(arr) do
begin
x := arr[i];
if x < min1 then
begin
// x becomes the new smallest; old min1 becomes min2
min2 := min1;
min1 := x;
end
else if x < min2 then
begin
// x is not the smallest, but smaller than the second smallest
min2 := x;
end;
end;
// The minimal sum of two distinct elements
Result := min1 + min2;
end;
var
arr: array of Integer;
result: Integer;
begin
arr := [7, -3, 10, 1, 5, 2, 4];
try
result := MinimalTwoSum(arr);
WriteLn('Minimal sum of two elements: ', result);
except
on E: Exception do
WriteLn('Error: ', E.Message);
end;
end.
{
run:
Minimal sum of two elements: -2
}
