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.

Checkout our next problem.

LEAVE A REPLY