Print All Pairs With Given Sum

Let's start by understanding the problem statement of this task.

You are given an array and an integer, your work is to print all possible pairs which form the given difference.

Hint:

For printing, all possible pairs one may use an unordered map and can store the frequency of each integer and print the possible integers in the map with the help of their frequency as using an unordered map one can find the elements easily in less time complexity.

Quick Think:

For designing the above algorithm, we have to look into the following points:-

• The frequency of the elements should be stored into the unordered map and the number of times the occurrence of the element is found that the number of times the result should be printed.
• Use the unordered map for the above algorithm.
• If the element is found in the map, then print the difference, else store the frequency of the element in the map.

Algorithm:

Create a function with the arguments as the array and the size of the array, and follow the steps below to reach the solution:-

Step1: Define the unordered map.

Step2: Now, start traversing the array and store the element to be found in the map as the difference of the given sum and the first element in the array if found then go to step 3 else go to step 5.

Step3: Now, store the count of the second number found in the array.

Step4: Now, print the pairs the number of times the second integer is found in the map.

Step5: Store the count of the second element in the map.

Implementation Of The Above Algorithm:

Now let's see the implementation of the above algorithm,

#include <bits/stdc++.h>
using namespace std;
/*Function to find pairs. */
void findpair(int arr[], int result, int n)
{
	unordered_map<int, int> map;
	for (int i = 0; i < n; i++)
	{
		int diff = result - arr[i];
		if (map.find(diff) != map.end())
		{
			int count = map[diff];
			for (int j = 0; j < count; j++)
				cout << "(" << diff << ", " <<
				arr[i] << ")" << endl;
		}

		map[arr[i]]++;
	}
}

// Driver function to test the above function
int main()
{
	int arr[] = { 2, 5, 17, -1 };

	int n = sizeof(arr) / sizeof(arr[0]);
	int sum = 7;
	findpair(arr, sum, n);
	return 0;
}

The time complexity of the above algorithm: O(c + n) where c is the count of pairs.

The output of the above algorithm: (2, 5).

Explanation Of The Above Algorithm:

Consider the array as shown in the above diagram and follow the steps below to reach the desired output:

• Now, after the declaration of the unordered map we have the first array element as 2, now since the difference of the given number and 2 is not in the map so, insert the frequency of the element 2 which is 1 in the map as shown in the diagram above.

• Now, move to the next element of the array which is 5 again, now, since the difference between the given number and the element 5 is present in the map with frequency of 1, so we print our result as shown in the diagram above.

• Again, moving to the next element we have 17 again, since the difference of the given element and the current element is not found in the map so, insert the frequency of the element 17 which is 1 in the map as shown in the diagram above.

• Again, moving to the next element we have -1 again, since the difference of the given element and the current element is not found in the map so insert the frequency of the element -1 which is 1 in the map as shown in the diagram above.
• Now, we get our result as the output.