Python List Advanced Exercise - List all pairs whose sum equals a given value

Last update on December 21 2024 07:33:59 (UTC/GMT +8 hours)

Write a Python program to find all the pairs in a list whose sum is equal to a given value.

Sample Solution:

Python Code:

# Define a function to find all pairs in a list that sum up to a given value
def pairs_with_sum(lst, g_sum):
    # Create an empty dictionary 'complement_dict' to store complements of visited numbers
    complement_dict = {}
    # Create an empty list 'pairs' to store the pairs that sum up to the target value
    pairs = []
    # Iterate through the elements in the input list 'lst'
    for num in lst:
        # Calculate the complement of the current number with respect to the target value
        complement = g_sum - num
        # Check if the complement is already in 'complement_dict'
        if complement in complement_dict:
            # If found, add the current number and its complement as a pair to 'pairs'
            pairs.append((num, complement))
        else:
            # If not found, store the complement in 'complement_dict' for future checks
            complement_dict[num] = complement
    # Return the list of pairs that sum up to the target value
    return pairs

# Create a list of numbers
nums = [1, 2, 3, 4, 5, 6, 7, 8, 9]
# Set a target sum 'val'
val = 10

# Print the original list of numbers
print("Original list:")
print(nums)

# Call the pairs_with_sum function with the list of numbers and the target sum 'val', and store the result in 'result'
result = pairs_with_sum(nums, val)

# Print the result, which is a list of pairs that sum up to 'val'
print("List all pairs of the said list whose sum equals to", val)
print(result)

# Update the target sum 'val'
val = 35

# Print the original list of numbers
print("\nOriginal list:")
print(nums)

# Call the pairs_with_sum function with the updated target sum 'val' and the same list of numbers, and store the result in 'result'
result = pairs_with_sum(nums, val)

# Print the result, which is a list of pairs that sum up to the updated 'val'
print("List all pairs of the said list whose sum equals to", val)
print(result)

# Update the target sum 'val' again
val = 5

# Print the original list of numbers
print("\nOriginal list:")
print(nums)

# Call the pairs_with_sum function with the updated target sum 'val' and the same list of numbers, and store the result in 'result'
result = pairs_with_sum(nums, val)

# Print the result, which is a list of pairs that sum up to the updated 'val'
print("List all pairs of the said list whose sum equals to", val)
print(result) 

Sample Output:

Original list:
[1, 2, 3, 4, 5, 6, 7, 8, 9]
List all pairs of the said list whose sum equals to 10
[(6, 4), (7, 3), (8, 2), (9, 1)]

Original list:
[1, 2, 3, 4, 5, 6, 7, 8, 9]
List all pairs of the said list whose sum equals to 35
[]

Original list:
[1, 2, 3, 4, 5, 6, 7, 8, 9]
List all pairs of the said list whose sum equals to 5
[(3, 2), (4, 1)]

Flowchart:

What is the time complexity and space complexity of the following Python code?

def pairs_with_sum(lst, g_sum):
    complement_dict = {}
    pairs = []
    for num in lst:
        if g_sum - num in complement_dict:
            pairs.append((num, g_sum - num))
        else:
            complement_dict[num] = g_sum - num
    return pairs

Time complexity - The time complexity of the said code is O(n), where n is the length of the input list “lst”. This is because the code iterates over the input list once and performs constant time operations in each iteration. The time complexity of dictionary operations such as in (within if condition) and [] is O(1) on average, assuming a good hash function.

Space complexity - The space complexity of the code is also O(n), since in the worst case all elements of the input list may be stored in the dictionary.

Python Code Editor:

Previous: Sort a list of dictionaries based on values of a key.