Count pairs with a given sum
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