How to find the minimal possible sum of two distinct elements in a list with Python

1 Answer

0 votes
"""
    Goal:
    -----
    Find the minimal value of (a[i] + a[j]) for any two distinct elements in a list.

    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 list 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.
def minimal_two_sum(lst):
    # Handle edge case: need at least two elements
    if len(lst) < 2:
        raise ValueError("List must contain at least two elements.")

    # Initialize min1 and min2 to very large values
    min1 = float("inf")
    min2 = float("inf")

    # Single pass through the List
    for x in lst:
        if x < min1:
            # x becomes the new smallest; old min1 becomes min2
            min2 = min1
            min1 = x
        elif 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


def main():
    lst = [7, -3, 10, 1, 5, 2, 4]

    try:
        result = minimal_two_sum(lst)
        print("Minimal sum of two elements:", result)
    except Exception as e:
        print("Error:", e)


if __name__ == "__main__":
    main()


"""
run:

Minimal sum of two elements: -2

"""

 



answered Jul 21 by avibootz
...