Count Pairs with Given Sum

Welcome to our lesson on Count Pairs with Given Sum! This is an essential problem that every programmer should know, as it helps you understand and apply important concepts in Data Structures and Algorithms. Let's dive in!

Understanding the Problem

Given an array of integers and a target sum, the goal is to count the number of pairs in the array whose sum equals the target sum. This problem is a great way to learn about hash maps (or dictionaries in some languages) and their usefulness in solving various complex problems.

💡 Pro Tip: The time complexity of this solution is O(n), where n is the number of elements in the array, making it highly efficient.

Pseudocode

Initialize an empty hash map (or dictionary) to store the frequencies of numbers in the array.
Iterate through the array, for each number num, do the following:
1. If the target sum minus num is in the hash map, increment the count by 1.
2. If not, add num to the hash map.
Return the count at the end.

Example

Let's consider an array [1, 2, 3, 4, 5] and the target sum 7.

📝 Note: We will use Python for our examples. Feel free to translate these concepts to your preferred programming language.

python

def count_pairs(arr, target):
    count = 0
    freq = {}

    for num in arr:
        if target - num in freq:
            count += freq[target - num]
        freq[num] = freq.get(num, 0) + 1

    return count

print(count_pairs([1, 2, 3, 4, 5], 7))  # Output: 2

In this example, the pairs that sum up to 7 are (1, 6) and (2, 5). The function count_pairs correctly counts and returns 2.

Advanced Example

Let's consider a larger array [1, 2, 3, 4, 5, 6, 7, 8, 9] and the target sum 12.

python

print(count_pairs([1, 2, 3, 4, 5, 6, 7, 8, 9], 12))  # Output: 5

In this case, the pairs that sum up to 12 are (1, 11), (2, 10), (3, 9), (4, 8), and (5, 7).

That's all for today! We hope you enjoyed learning about counting pairs with a given sum. Stay tuned for more engaging lessons on Data Structures and Algorithms here at CodeYourCraft!

🎯 Practice Question: Implement the count_pairs function in your favorite programming language and test it with different arrays and target sums. Share your solutions in the comments below!