Number of Pairs which sum equal to the target
Question:
Find the Number of Pairs which sum is equal to the given target
Example:
[1, 5, 4, 3, 3, 7, 1, 2]
Target = 6
Output: 4 Pairs (1,5) (5,1) (4,2) (3,3)
Number of Pairs in an array:
Approach 1:
Logic:
- Initialise the Hash-Map
- Check the element in Hash-Map which is subtracted the from array element with target value
- If element found then get the value of the key from Hash-Map and add into the count
- Otherwise insert element into the Hash-Map with value of 1
- If already present increment the key’s value
- At last print the count of pairs present in array
Explanation:
Program:
Java:
[code lang=”java”]
import java.util.HashMap;
public class FindTargetPairInArray{
static void findTargetPairInArray(int array[], int target)
{
HashMap<Integer,Integer> element = new HashMap<>();
int length = array.length;
int count = 0;
int value = 0;
for (int i = 0; i < length; i++) {
if (element.containsKey(target – array[i])) {
//add the count with value of HashMap
count += element.get(target – array[i]);
value = element.get(target – array[i]);
//Print the pairs
while(value != 0)
{
System.out.println("(" + array[i] + ", " +(target – array[i])+")");
value–;
}
}
//Insert the key into the HashMap
if(element.containsKey(array[i])){
element.put(array[i], element.get(array[i])+1);
}
else{
element.put(array[i], 1);
}
}
System.out.println("Count of pairs: "+ count );
}
public static void main(String[] args)
{
int array[] = { 1, 5, 4, 3, 3, 7, 1, 2};
int target = 6;
findTargetPairInArray(array, target);
}
}
[/code]
Approach 2:
Logic:
- Check the element is greater than or equal to target
- If yes then no need to do below operations, continue with next element
- Add every element with every other element in the array
- Then check the value equal to target or not
- If yes increment the count and at last print the Number of Pairs
Explanation:
Program:
C:
[code lang=”c”]
#include <stdio.h>
void main()
{
int arr[] = { 1, 5, 4, 3, 3, 7, 1, 2};
int target = 6;
int count = 0;
int length = sizeof(arr)/sizeof(arr[0]);
//Check the pairs
for(int i = 0; i < length – 1; i++)
{
//skip if element is greater than or equal to target
if(arr[i] >= target)
continue;
for(int j = i + 1; j < length; j++)
{
if(arr[i] + arr[j] == target)
{
count++;
printf("(%d %d)", arr[i], arr[j]);
}
}
}
printf("\nCount of pairs: %d",count);
}
[/code]
