#include <iostream>
#include <vector>
#include <limits>
/*
Goal:
-----
Find the minimal value of (a[i] + a[j]) for any two distinct elements in a vector.
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 vector once, keeping track of:
- min1 = smallest element seen so far
- min2 = second smallest element seen so far
*/
// A function that computes the minimal sum of two distinct elements.
int minimal_two_sum(const std::vector<int>& vec) {
// Handle edge case: need at least two elements
if (vec.size() < 2) {
throw std::invalid_argument("Vector must contain at least two elements.");
}
// Initialize min1 and min2 to very large values
int min1 = std::numeric_limits<int>::max();
int min2 = std::numeric_limits<int>::max();
// Single pass through the vector
for (int x : vec) {
if (x < min1) {
// x becomes the new smallest; old min1 becomes min2
min2 = min1;
min1 = x;
} else if (x < min2) {
// x is not the smallest, but smaller than the second smallest
min2 = x;
}
}
// The minimal sum of two distinct elements
return min1 + min2;
}
int main() {
std::vector<int> vec = {7, -3, 10, 1, 5, 2, 4};
try {
int result = minimal_two_sum(vec);
std::cout << "Minimal sum of two elements: " << result << "\n";
} catch (const std::exception& e) {
std::cerr << "Error: " << e.what() << "\n";
}
}
/*
run:
Minimal sum of two elements: -2
*/
