Pairs with given sum k in an array

Greetings reader, in this article we are going to cover how to output pairs of elements with a given sum k in an array. Without further adieu let us proceed.

The problem here is to take an array and a sum as input from the user and print pairs of elements which on summation give the given sum. For example, say the array=[1,2,3,4] and sum = 4, then the output should be (1,3).

There are a number of methods to solve this problem, here we are going to take a look at two popular methods, namely Brute Force Method and Hashing Method. Let us take a close look at both of these.

Brute Force Algorithm

The brute force method as the name suggests is basically using all of the computational power available to solve the problem. It checks for all possible combinations using two loops. This algorithm isn’t a very efficient one but provides very accurate output.

Pseudocode

1. ​Get the array from the user as, A.
   
2. Get the sum as, k.
   
3. Set i=0, j=i+1, flag=0.
   
   1. if(A[i]+A[j]=k),
      
      1. then print( A[i], A[j])
         
      2. Increment flag=1
         
   2. j++
      
4. Repeat step 3 until j=n-1
   
   1. i++
5. Repeat step 3 and 4 until i=n-1
   

So in the Brute force algorithm, we take the Array, A and the sum, k from the user. We then use two nested loops and check if the sum of A[i]+A[j] = k. If the sum matches, we print the pair. We then finally check for the flag variable to see if we found any pairs, if not we print “No pairs found”.

Time Complexity

For worst case, we have to compare all possible combinations,

Total no. of possible pairs $= nC2 = n(n-1)/2 = O(n^2)$

Code

#include <stdio.h>

void main()
{
    int flag = 0, i = 0, A[20], n, k;

    printf("Enter number of elements in the array: ");
    scanf("%d", &n);

    printf("Enter the array elements: ");
    while (i < n)
    {
        scanf("%d", &A[i]);
        i++;
    }

    printf("Enter the sum: ");
    scanf("%d", &k);

    for (i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            if (A[i] + A[j] == k)
            {
                printf("(%d,%d) \n", A[i], A[j]);
                flag = 1;
            }
        }
    }

    if (flag == 0)
    {
        printf("No pairs found.");
    }
}

import java.util.Scanner;
public class PairsWithSum
{
   static void findThePairs(int inputArray[], int inputNumber)
   {
       System.out.println("Pairs of elements whose sum is "+inputNumber+" are : ");

       for (int i = 0; i < inputArray.length; i++)
       {
           for (int j = i+1; j < inputArray.length; j++)
           {
               if(inputArray[i]+inputArray[j] == inputNumber)
               {
                   System.out.println(inputArray[i]+","+inputArray[j]);
               }
           }
       }
   }

   public static void main(String[] args)
   {   PairsWithSum p = new PairsWithSum();
       int n, sum = 0,k;
       Scanner s = new Scanner(System.in);
       System.out.print("Enter no of elements in array:");
       n = s.nextInt();

       int A[] = new int[n];
       System.out.println("Enter all the elements:");
       for(int i = 0; i < n; i++)
       {
           A[i] = s.nextInt();
       }

       System.out.print("Enter the sum:");
       k = s.nextInt();
       p.findThePairs( A, k);
   }
}

flag = 0
A = []
n = int(input("enter number of elements "))
print("enter the array ")
for i in range(0, n):
    ele = int(input())
    A.append(ele)
print(A)
k = int(input("enter the sum: "))
for i in range(0, n):
    for j in range(i + 1, n):
        if A[i] + A[j] == k:
            print(A[i], ",", A[j], "\n")
            flag = 1
if flag == 0:
    print("No pairs found")

Hashing Algorithm

The hash function allows the user to map a given value with a particular key to allow faster access of data. Hashing enables us to create more efficient and faster programs with fewer lines of code.

To solve this problem, we first initialize a hash table. Then check if the sum, k minus the element in the hash table gives us another element in the hash table, if yes we print the pair. We repeat this step for all elements in the array. 

Pseudocode

1. ​Create a hash table, hashs.
   
2. Get array, A and sum, k from user
   
3. For i<length(A) 
   
   1. t= k - A[i] 
      
   2. If t in hashes,then print(A[i],t). 
      

In the hashing algorithm, we first create a hash table and then get the array,A and the sum,k from the user. We then check if a temp value, t = k- A[i] belongs in the hash table we created. If yes, we print t and A[i]. We repeat this for all elements in A. 

Code

#include <stdio.h>
#define MAX 100000

void PairsWithHash(int arr[], int arr_size, int sum)
{
    int i, t;
    int flag = 0;

    _Bool s[MAX] = {0}; /*initialize hash set as 0*/

    for (i = 0; i < arr_size; i++)
    {
        t = sum - arr[i];
        if (s[t] == 1)
        {
            printf("Pairs are: (%d, %d) \n", arr[i], t);
            flag = 1;
        }

        s[arr[i]] = 1;
    }
    if (flag == 0)
    {
        printf("No pairs found");
    }
}

void main()
{
    int i = 0, A[20], n, k;

    printf("Enter number of elements in the array: ");
    scanf("%d", &n);

    printf("Enter the array elements: ");
    while (i < n)
    {
        scanf("%d", &A[i]);
        i++;
    }

    printf("Enter the sum: ");
    scanf("%d", &k);
    PairsWithHash(A, n, k);
}

import java.util.*;

public class PairWithSumHash {
   static void findThePairs(int arr[], int sum) {


       HashMap<Integer, Integer> hashs = new HashMap<Integer, Integer>(); //initiate the hash


       for (int i = 0; i < arr.length; i++) {


           int t = sum - arr[i];
           if (hashs.containsKey(t)) {
               int count = hashs.get(t);

               for (int j = 0; j < count; j++)
                   System.out.print("(" + t + ", " + arr[i] +")" + "\n");
           }
           if (hashs.containsKey(arr[i])) {
               hashs.put(arr[i], hashs.get(arr[i]) + 1);
           } else {
               hashs.put(arr[i], 1);
           }
       }
   }



   public static void main(String[] args)
   {
       PairWithSumHash p = new PairWithSumHash();
       int n, sum = 0,k;
       Scanner s = new Scanner(System.in);
       System.out.print("Enter no of elements in array:");
       n = s.nextInt();

       int A[] = new int[n];
       System.out.println("Enter all the elements:");
       for(int i = 0; i < n; i++)
       {
           A[i] = s.nextInt();
       }

       System.out.print("Enter the sum:");
       k = s.nextInt();
       p.findThePairs( A, k);
   }
}

def pairs(A, k):
    hashs = set()  # Initialize a hash set
    flag = 0
    if len(A) < 2:
        print("Array has too few elements")

    for i in range(0, len(A)):
        t = k - A[i]
        if t in hashs:
            print("(" + str(A[i]) + ", " + str(t) + ")")
            flag = 1
        hashs.add(A[i])
    if flag == 0:
        print("No pairs found.")


A = []
n = int(input("enter number of elements "))
print("enter the array ")
for i in range(0, n):
    ele = int(input())
    A.append(ele)
print(A)
k = int(input("enter the sum: "))
pairs(A, k)