Introduction to Microservice Architecture Using SpringBoot - Part 1

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.

Example 2:

Input:
N = 4, X = 2
arr[] = {1, 1, 1, 1}
Output: 6
Explanation: 
Each 1 will produce sum 2 with any 1.

Company Tags

 Accolite Adobe Amazon FactSet Flipkart Goldman Sachs Hike MakeMyTrip Salesforce

Solution

 import java.io.*;  
 import java.util.*;  
 public class GFG {  
   public static void main(String[] args) throws Exception {  
     BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
     int tc = Integer.parseInt(br.readLine().trim());  
     while (tc-- > 0) {  
       String[] inputLine;  
       inputLine = br.readLine().trim().split(" ");  
       int n = Integer.parseInt(inputLine[0]);  
       int k = Integer.parseInt(inputLine[1]);  
       int[] arr = new int[n];  
       inputLine = br.readLine().trim().split(" ");  
       for (int i = 0; i < n; i++) {  
         arr[i] = Integer.parseInt(inputLine[i]);  
       }  
       int ans = new Solution().getPairsCount(arr, n, k);  
       System.out.println(ans);  
     }  
   }  
 }   
 class Solution {  
   int getPairsCount(int[] arr, int n, int k) {  
     // code here  
     int i,count=0;  
     HashMap<Integer,Integer> hs= new HashMap<>();  
     for(i=0;i<n;i++)  
     {  
       if(hs.containsKey(arr[i]))  
       hs.put(arr[i],hs.get(arr[i])+1);  
       else  
       hs.put(arr[i],1);  
     }  
     for(i=0;i<n;i++)  
     {  
       if(hs.containsKey(k-arr[i]))  
       {  
         hs.put(arr[i],hs.get(arr[i])-1);  
         count+=hs.get(k-arr[i]);  
       }  
     }  
     return count;  
   }  
 }  

Question Link : https://practice.geeksforgeeks.org/problems/count-pairs-with-given-sum5022/1#