Program to Find a Pair with the Given Sum in an Array

Python Program to Find a Pair with the Given Sum in an Array

by

Are you wondering how to seek help from subject matter experts and learn the Java language? Go with these Basic Java Programming Examples and try to code all of them on your own then check with the exact code provided by expert programmers.

Lists in Python:

A list is a data structure or a container that may hold numerous pieces of information at once. There will be an order to the list, and it will be counted. The elements are indexed in a sequential order, with 0 as the initial index. Each element will have its own location in the sequence, and if the same value appears in the sequence numerous times, each will be treated as a separate and different element.

Given a list and a number k the task is to find a pair with the given sum k.

Examples:

Example1:

Input:

given list=[5,9,2,8,7,6]
value=10

Output:

Pair with given sum of elements is found

Example2:

Input:

given list=[4,7,6,1,8,9,3,4,5]
value=2

Output:

Pair with given sum of elements is not found

Program to Find a Pair with the Given Sum in an list in Python

There are several ways to find a pair with the given sum k in a list some of them are:

Drive into Python Programming Examples and explore more instances related to python concepts so that you can become proficient in generating programs in Python Programming Language.

Method #1:Using Nested loops(Brute Force Approach)

For each pair i , j in A[], use two loops and check A[i] + A[j] == K. Return true if there is a pair with a sum equal to K. If you didn’t locate such a pair by the end of both loops, return false.

Below is the implementation:

# function which returns true if the pair with given sum k exists
# else it will return false


def checkPair(givenlist, value):
  # calculating the length of given list
    length = len(givenlist)
   # Traversing all elements in given list except the last
    for i in range(length - 1):

        # iterating from i+1 element to last element
        for j in range(i + 1, length):

            # if the given sum "value" is found then return true
            if givenlist[i] + givenlist[j] == value:
                # pair is found so it should return true
                return True

    # if no pair is found then we should return true
    return False


# given list
given_list = [5, 9, 2, 8, 7, 6]
# given element k
value = 10
# passing the given list and value to checkPair function
if(checkPair(given_list, value)):
    print("Pair with given sum of elements is found")
else:
    print("Pair with given sum of elements is not found")

Output:

Pair with given sum of elements is found

Time Complexity:

Here we use 2 loops so it takes average Time Complexity of O(n^2). To increase the efficiency of the above program we have other methods such as sorting and hashing

sorting technique:

The goal is to sort the provided list in ascending order while maintaining search space by keeping two indices (low and high) that initially point to two array endpoints. Then, for each iteration of the loop, reduce the search space list[low…high] by comparing the total of elements existing at indices low and high to the desired sum. If the sum is less than the expected amount, increment low; otherwise, decrement high if the sum is greater than the desired sum. Return the pair if it is found.

Time Complexity of sorting technique:

It takes O(nlogn) time complexity to achieve this task because we have to sort the given list so there is another best way to solve this question that is using hashing technique which we will discuss below

Method #2:Using Hashing

We can solve this problem in linear time by using a hash table. The plan is to put each array element list[i] into a map. We also check to see if the difference (list[i], sum – list[i]) already exists in the map. If the difference has already been seen, print the pair and return.

Below is the implementation:

# function which returns true if the pair with given sum k exists
# else it will return false


def checkPair(givenlist, value):
  # calculating the length of given list
    length = len(givenlist)
    # taking a empty dictionary
    dictionary = {}

    # using enumerate we check elements in givenlist
    for i, ele in enumerate(givenlist):

        # checking if the pair value-ele exists in guven dictionary
        # if it exists then return true
        if value - ele in dictionary:
            return True

        # storing index of curreent item in given dictionary as key
        dictionary[ele] = i

    # if no pair is found then we will return False
    return False


# given list
given_list = [5, 9, 2, 8, 7, 6]
# given element k
value = 10
# passing the given list and value to checkPair function
if(checkPair(given_list, value)):
    print("Pair with given sum of elements is found")
else:
    print("Pair with given sum of elements is not found")

Output:

Pair with given sum of elements is found

Time Complexity:

This above program takes O(n) Time Complexity which is most efficient way to do the abovee program abut it takes O(n) Space Complexity to achieve this task.

Related Programs:

Leave a Comment