Problem Statement: Find Pairs with Given Sum
You are given an array of integers arr and an integer target. Write a Python function find_pairs_with_given_sum(arr, target) that finds all pairs of elements from the array that sum up to the target sum.
Function Signature:
def find_pairs_with_given_sum(arr: List[int], t: int) -> List[Tuple[int, int]]:
"""
Finds pairs of elements from the array that sum up to the target sum.
Parameters:
arr (List[int]): List of integers.
t (int): Target sum.
Returns:
List[Tuple[int, int]]: List of tuples containing pairs of elements that sum up to the target sum.
"""
Input Format:
The first line of input contains an integer n (1 ≤ n ≤ 10^5), denoting the size of the array.
The second line contains n space-separated integers representing the elements of the array.
The third line contains an integer target (−10^9 ≤ target ≤ 10^9), denoting the target sum.
Output Format:
For each pair of elements that sum up to the target, print the pair in the format a + b = target, where a and b are the elements of the pair and target is the given target sum.
Sample Input:
6
1 2 3 4 5 6
7
Sample Output:
4 + 3 = 7
5 + 2 = 7
6 + 1 = 7
Test Cases:
Input:
5
-1 2 3 -2 5
0
Output:
-2 + 2 = 0
Input:
3
10 20 30
50
Output:
30 + 20 = 50
Input:
4
-5 -10 15 20
10
Output:
15 + -5 = 10
20 + -10 = 10
SOLUTION:
def find_pairs_with_given_sum(arr, t):
hash_table = {}
pairs = []
for i in arr:
complement = t - i
if complement in hash_table:
pairs.append((i, complement))
hash_table[i] = True
return pairs
n = int(input())
arr = list(map(int, input().split()))
target = int(input())
result = find_pairs_with_given_sum(arr, target)
for i in result:
print(i[0], "+", i[1],"=",target)
- The function achieves linear time complexity O(n) where n is the size of the input array arr. This efficiency is due to iterating through the array only once.
- The function utilizes extra space to store elements in the hash table. The space complexity is O(n) due to the worst-case scenario where all elements of the array are unique.
- The function employs a hash table to store elements encountered while iterating through the array. This hash table facilitates constant-time lookups for checking the existence of a complement.
- For each element i in the array, the function calculates its complement as complement = t - i, where t is the target sum. This calculation determines the value needed to form a pair summing up to the target.
- If the complement exists in the hash table, the function identifies a pair (i, complement) that sums up to the target. It then appends this pair to the pairs list.
- The function utilizes a list to store pairs of elements that sum up to the target. This approach ensures efficient appending of pairs without needing to pre-allocate memory.
- The hash table serves as a data structure to efficiently store elements encountered in the array. It enables constant-time lookups to determine whether a complement exists in the array.
- The function returns a list of tuples representing pairs of elements that sum up to the target. Each tuple consists of two elements (i, complement).
- After calling the function and obtaining the result, the provided code snippet iterates through the list of pairs and prints them in a formatted manner, displaying each pair as i + complement = target. This ensures clear presentation of the pairs found.
Comments
Post a Comment