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);
}
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;
}
}
Top comments (0)