Saturday, July 6, 2019

Count pairs with given sum using Hashing

Problem Statement:


Given an array of integers, and an integer  ‘K’ , find the count of pairs of elements in the array whose sum is equal to 'K'.

Input:
First line of the input contains an integer T, denoting the number of test cases. Then T test cases follow. Each test case consists of two lines. First line of each test case contains 2 space separated integers N and K denoting the size of array and the sum respectively. Second line of each test case contains N space separated integers denoting the elements of the array.

Output:
Print the count of pairs of elements in the array whose sum is equal to the K.

Constraints:
1<=T<=50
1<=N<=50
1<=K<=50
1<=A[i]<=100

Example:
Input

2
4 6
1  5  7 1
4 2
1 1 1 1
Output
2
6


Solution:


import java.util.*;
import java.lang.*;
import java.io.*;

class MuscleJava
{
    public static void main (String[] args)
    {
        Scanner s = new Scanner(System.in);
        int t = s.nextInt();
        while(t-->0)
        {
            int n = s.nextInt();
            int k = s.nextInt();
            int arr[] = new int[n];
            int count = 0;
            HashMap<Integer,Integer> h = new HashMap();
            for(int i=0; i<n; i++)
            {
                arr[i] = s.nextInt();
                int temp = arr[i];
                if(!h.containsKey(arr[i]))
                    h.put(temp,0);
                h.put(temp, h.get(temp)+1 );
            }
            for(int i=0; i<n; i++)
            {
                if(h.get(k-arr[i]) != null)
                {
                    count += h.get(Math.abs(k-arr[i]));
                }
               
                if(arr[i]+arr[i] == k)
                    count--;
            }
            System.out.println(count/2);
        }
    }
}
 

No comments:

Post a Comment