DEV Community

Cover image for Count Pairs with given Sum
Tisha Agarwal
Tisha Agarwal

Posted on

Count Pairs with given Sum

Given an array of N integers, and an integer K, find the number of pairs of elements in the array whose sum is equal to K.

Example 1:
Input:
N = 4, K = 6
arr[] = {1, 5, 7, 1}
Output: 2
Explanation:
arr[0] + arr[1] = 1 + 5 = 6
and arr[1] + arr[3] = 5 + 1 = 6.

It is a EASY LEVEL question but asked in many companies like Amazon, Accolite, Adobe, Flipkart, Hike, MakeMyTrip etc.

_If you want to solve the question click here:(_https://practice.geeksforgeeks.org/problems/count-pairs-with-given-sum5022/1#)

Approach 1:
The idea is to iterate one loop from i=0 to the end of the array and the second loop from j=i+1 to the end of the array. This is the Brute force approach, with Time Complexity:O(n^2)

public static void getPairsCount(int[] arr, int sum)
    {

        int count = 0; // Initialize result

        // Consider all possible pairs and check their sums
        for (int i = 0; i < arr.length; i++)
            for (int j = i + 1; j < arr.length; j++)
                if ((arr[i] + arr[j]) == sum)
                    count++;

        System.out.printf("Count of pairs is %d", count);
    }
Enter fullscreen mode Exit fullscreen mode

Approach 2:
(i) Sort the array.
(ii) Two pointer approach: Start one pointer from i=0 and the other from j=arr.length-1.
(iii)-Greater than the sum then decrement j.
-Lesser than the sum then increment i.
-Equals to the sum then count such pairs.
Time Complexity: O(nlogn+n)

Approach 3:
This is the optimized method to solve the problem.
here we are going to use HashMap.
Time Complexity: O(n)
Space Complexity: ~O(n)

JAVA CODE

import java.util.*;
public class CountPairs_G_Sum {
    public static void main(String[] args)
    {
        Scanner sc=new Scanner(System.in);
        System.out.println("Enter the size of the array:");
        int n=sc.nextInt();
        System.out.print("Enter the value of k: ");
        int k=sc.nextInt();
        int[] arr=new int[n];
        System.out.println("Enter the elements of the array: ");
        for(int i=0;i<n;i++)
        {
            arr[i]=sc.nextInt();
        }
        int res=getPairsCount(arr, n, k);
        System.out.println(res);
    }
    public static int getPairsCount(int arr[],int n,int k)
    {
        int c=0;//counter
        HashMap<Integer,Integer> hm=new HashMap<Integer,Integer>();
        for(int i=0;i<n;i++)
        {
            if(arr[i]<k)
            {
                int element=k-arr[i];
                if(hm.containsKey(element))
                {
                    c+=hm.get(element);
                }
                if(hm.get(arr[i])==null)//if element is not present in the HashMap
                {
                    hm.put(arr[i],0);
                }
                hm.put(arr[i],hm.get(arr[i])+1);
            }
        }
        return c;
    }   
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)