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