Let's suppose we have an array of
Some examples of this problem are given below:
Input: array = {-1, 2, 4, 1, 0, -5, 5, 3}, sum = 5
Output: 3
Explanation: Pairs with sum=5 are (4, 1), (0, 5), (2, 3).
Input: array = {-4, -2, 1, 3, 2, 4}, sum = 0
Output: 2
Explanation: Pairs with sum=0 are (-4, 4), (-2, 2).
Input: array = {-4, -1, 3, 0, 4, 1}, sum = -2
Output: 0
Explanation: There are no pairs in the array with the sum -2.
We iterate over the array and check every element, with all the elements that come after it in the array.
We sum those pairs of elements and compare them with the given sum. We increment the counter if it is equal to the given sum.
In the end, we return the counter.
The code for this algorithm is as follows:
#include <iostream>using namespace std;int countPairs(int arr[], int sum, int length) {// int length = sizeof(arr)/sizeof(int);int count = 0;if(length == 0) // Return 0 with an empty arrayreturn 0;for(int i = 0; i < length - 1; i++)for(int j = i + 1; j < length; j++) {if(arr[i] + arr[j] == sum)count++;}return count;}// Driver codeint main() {int inp_arr[] = {-1, 2, 4, 1, 0, -5, 5, 3};int sum = 5;int length = sizeof(inp_arr)/sizeof(int);// Print the arraycout << "Input array: ";for(int i = 0; i < length; i++) {cout << inp_arr[i] << ' ';}cout << "\nThere are " << countPairs(inp_arr, sum, length) << " pairs with sum = " << sum;return 0;}
The explanation for this code is as follows:
Lines 8–9: If the input array is empty, then the function returns 0.
Lines 10–11: These are the nested loops to iterate over the entire array.
Line 12: We add every element iterated by the outer loop arr[i]
to every element that comes after it in the array iterated by the inner loop arr[j]
. Then, we compare it with the given sum
.
Line 13: We increment the counter if we find a pair that sums to the given variable sum
.
On each iteration of the outer loop, the inner loop iterates a maximum of
We don't use any temporary data structures to store any values of the array. We only use the original array for all our calculations, and an integer variable count
to store the number of pairs found. Thus, the space complexity of this algorithm is
Free Resources