Finding a Pair with the Given Sum in an Array

Finding a Pair with the Given Sum in an Array

Given an unsorted integer array, we need to find a pair of numbers in the array that add up to a given sum. If such a pair exists, we will return the pair of numbers. Otherwise, we will indicate that no pair was found.

Problem Statement

Let’s consider the following problem:

Given an unsorted integer array and a target sum, we need to find a pair of numbers in the array that add up to the target sum.

Example 1:

Input: nums = [8, 7, 2, 5, 3, 1], target = 10

Output: Pair found (8, 2) or Pair found (7, 3)

Example 2:

Input: nums = [5, 2, 6, 8, 1, 9], target = 12

Output: Pair not found

Solution

There are multiple approaches to solve this problem. Here, we will discuss two commonly used approaches:

1. Brute Force Approach
2. Hashing Approach

1. Brute Force Approach

The brute force approach involves checking each pair of numbers in the array to see if their sum equals the target sum. We can achieve this by using two nested loops. The outer loop will iterate through each element in the array, and the inner loop will iterate through the remaining elements to find a pair.

Here is the step-by-step algorithm for the brute force approach:

1. Initialize two pointers, i and j, to iterate through the array.
2. Iterate through each element in the array using the outer loop (pointer i).
3. For each element, iterate through the remaining elements using the inner loop (pointer j).
4. Check if the sum of the current pair of numbers equals the target sum.
5. If a pair is found, return the pair.
6. If no pair is found after checking all possible pairs, return “Pair not found”.

2. Hashing Approach

The hashing approach involves using a hash table to store the difference between the target sum and each element in the array. We can then check if the difference exists in the hash table. If it does, we have found a pair that adds up to the target sum.

Here is the step-by-step algorithm for the hashing approach:

1. Create an empty hash table.
2. Iterate through each element in the array.
3. Calculate the difference between the target sum and the current element.
4. Check if the difference exists in the hash table.
5. If the difference exists, return the pair (current element, difference).
6. If the difference does not exist, add the current element to the hash table.
7. If no pair is found after checking all elements, return “Pair not found”.

Conclusion

In this blog post, we discussed the problem of finding a pair with the given sum in an array. We explored two approaches to solve this problem: the brute force approach and the hashing approach. Both approaches have their own advantages and disadvantages, and the choice of approach depends on the specific requirements of the problem.