Introduction
Example – A = [2, 4, 9, 1, 10, 5] , Sum = 6
Output – (2,4) or (1,5) as 2+4 = 6 and 1+5 = 6
Approach
3. Hashing – O(n) – As you traverse, map each element to dict/hashmap etc and check for the desired value in the map.
Video Demonstration
Run Time Complexities
Time – O(n^2)
Space – O(1)
Code
C++
#include <iostream>
#include <unordered_map>
// Function to find a pair in an array with a given sum using hashing
void findPair(int arr[], int n, int sum)
{
// create an empty map
std::unordered_map<int, int> map;
// do for each element
for (int i = 0; i < n; i++)
{
// check if pair `(arr[i], sum-arr[i])` exists
// if the difference is seen before, print the pair
if (map.find(sum - arr[i]) != map.end())
{
std::cout << "Pair found at index " << map[sum - arr[i]] <<
" and " << i;
return;
}
// store index of the current element in the map
map[arr[i]] = i;
}
// we reach here if the pair is not found
std::cout << "Pair not found";
}
int main()
{
int arr[] = { 8, 7, 2, 5, 3, 1};
int sum = 10;
int n = sizeof(arr)/sizeof(arr[0]);
findPair(arr, n, sum);
return 0;
}Java
class Main
{
// Naive method to find a pair in an array with a given sum
public static void findPair(int[] A, int sum)
{
// consider each element except the last
for (int i = 0; i < A.length - 1; i++)
{
// start from the i'th element until the last element
for (int j = i + 1; j < A.length; j++)
{
// if the desired sum is found, print it
if (A[i] + A[j] == sum)
{
System.out.println("Pair found at index " + i + " and " + j);
return;
}
}
}
// we reach here if the pair is not found
System.out.println("Pair not found");
}
public static void main (String[] args)
{
int[] A = { 8, 7, 2, 5, 3, 1 };
int sum = 10;
findPair(A, sum);
}
}Python
# Naive method to find a pair in a list with the given sum
def findPair(A, sum):
# consider each element except the last
for i in range(len(A) - 1):
# start from the i'th element until the last element
for j in range(i + 1, len(A)):
# if the desired sum is found, print it
if A[i] + A[j] == sum:
print("Pair found at index", i, "and", j)
return
# No pair with the given sum exists in the list
print("Pair not found")
if __name__ == '__main__':
A = [8, 7, 2, 5, 3, 1]
sum = 10
findPair(A, sum)You can use our online compiler to type and compile your code.
 – As you traverse, map each element to dict/hashmap etc and check for the desired value in the map.){kind=link}