Count pairs with a given sum

Published by hitman on

Given an array of integers, and a number ‘sum’, find the number of pairs of integers in the array whose sum is equal to ‘sum’.

Input : arr[] = {1, 5, 7, -1}, 
        sum = 6 
Output : 2 
Pairs with sum 6 are (1, 5) and (7, -1) 
Input : arr[] = {1, 5, 7, -1, 5}, 
        sum = 6 
Output : 3 
Pairs with sum 6 are (1, 5), (7, -1) & (1, 5) 
Input : arr[] = {1, 1, 1, 1}, 
        sum = 2 
Output : 6 
There are 3! pairs with sum 2. 
Input : arr[] = {10, 12, 10, 15, -1, 7, 6, 5, 4, 2, 1, 1, 1}, 
        sum = 11 
Output : 9

So the java code for the above program is:

public class CountPairs {

    static int retWidth(int[] arr,int sum)
    {
        int count = 0;
        HashMap<Integer,Integer> map = new HashMap<>();

        for(int i=0;i<arr.length;i++)
        {
            map.put(arr[i],map.getOrDefault(arr[i],0)+1);
        }

        for(int i=0;i<arr.length;i++)
        {
            int temp = sum - arr[i];
            if(map.containsKey(temp)) {

                count += map.get(temp);

                //Remove duplicates
                if(sum - arr[i] == arr[i])
                    count--;

            }
        }
        return count;
    }

    public static void main(String[] args)
    {
        int[] arr = {10, 12, 10, 15, -1, 7, 6,
                5, 4, 2, 1, 1, 1};
        int sum = 11;
        int count = retWidth(arr,sum);
        System.out.println(count/2);
    }

}

Time Complexity : O(n)


0 Comments

Leave a Reply

Your email address will not be published. Required fields are marked *