How to count pairs in an array with a given sum in C++

Understanding the problem

Let's suppose we have an array of $N$ integers, and a number or sum. We want to count the pairs of integers in the array that sum up to the given number.

Some examples of this problem are given below:

Example 1

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).

Example 2

Input: array = {-4, -2, 1, 3, 2, 4}, sum = 0
Output: 2
Explanation: Pairs with sum=0 are (-4, 4), (-2, 2).

Example 3

Input: array = {-4, -1, 3, 0, 4, 1}, sum = -2
Output: 0
Explanation: There are no pairs in the array with the sum -2.

Algorithm

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.

Code

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 array
    return 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 code
int main() {
  int inp_arr[] = {-1, 2, 4, 1, 0, -5, 5, 3};
  int sum = 5;
  int length = sizeof(inp_arr)/sizeof(int);
  // Print the array
  cout << "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;
}

Explanation

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.

Time complexity

On each iteration of the outer loop, the inner loop iterates a maximum of $N$ times, and the outer loop iterates $N - 1$ times. So, the maximum number of iterations can be $N^2$ , and the time complexity of this algorithm is $O(N^2)$ .

Space complexity

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 $O(1).$

Free Resources