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.
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.
For designing the above algorithm, we have to look into the following points:-
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.
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).
Consider the array as shown in the above diagram and follow the steps below to reach the desired output: