How to find the minimal possible sum of two distinct elements in an array with C

1 Answer

0 votes
#include <stdio.h>
#include <limits.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
*/

// A function that computes the minimal sum of two distinct elements.
int minimal_two_sum(const int *arr, int n) {
    // Handle edge case: need at least two elements
    if (n < 2) {
        // In C we cannot throw exceptions, so we print an error and return INT_MAX
        fprintf(stderr, "Array must contain at least two elements.\n");
        return INT_MAX;
    }

    // Initialize min1 and min2 to very large values
    int min1 = INT_MAX;
    int min2 = INT_MAX;

    // Single pass through the array
    for (int i = 0; i < n; i++) {
        int x = arr[i];

        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(void) {
    int arr[] = {7, -3, 10, 1, 5, 2, 4};
    int n = sizeof(arr) / sizeof(arr[0]);

    int result = minimal_two_sum(arr, n);

    if (result != INT_MAX) {
        printf("Minimal sum of two elements: %d\n", result);
    }

    return 0;
}


/*
run:

Minimal sum of two elements: -2

*/

 



answered Jul 21 by avibootz

Related questions

...