C program to find all pairs of integer array whose sum is equal to given number

In this blog post, we learn how to write a C program to find all pairs of an integer array whose sum is equal to a given sum? So here we will write the C program to find all pairs of an integer array whose sum is equal to a given number. We will also see how to display the number of pairs whose sum is equal to a given sum.

Example,

Input:  

int arr[] = {1, 5, 7, -1, 5};
element = 6


Output :  3


Explanation:

Three pairs are (1, 5), (7, -1) & (1, 5)

So let’s see the solution to find all pairs of an integer array whose sum is equal to a given number. Suppose arr is a given integer array of size N (arr[N] ), the task is to write the C program to count pairs with a given sum in an array.

Naive Solution:

It is a simple solution where traverse each element of the array and check if there’s another number in the array which can be added to it to give a sum.

 

#include <stdio.h>

//Calculate array size
#define ARRAY_SIZE(a)  sizeof(a)/sizeof(a[0])


// Naive method to count pair in an array with a given sum
int findPair(int arr[], int n, int sum)
{
    int i, j;
    int countPair = 0;

    // Consider all possible pairs and check their sums
    for (i = 0; i < n; i++)
    {
        // start from the i+1 element till the last element
        for (j = i + 1; j < n; j++)
        {
            // if the desired sum is found increment  counter
            if (arr[i] + arr[j] == sum)
            {
                countPair++;
            }
        }
    }
    return countPair;
}


int main()
{
    int arr[] = {1, 5, 7, -1, 5};
    int sum = 6;

    //find array size
    const int N = ARRAY_SIZE(arr);

    //get pairs in array
    const int pairCount = findPair(arr,N,sum);
    if(pairCount != 0)
    {
        printf("Count of pairs is %d",pairCount);
    }
    else
    {
        printf("Pair Not found");
    }

    return 0;
}

Output

C program to find all pairs of an integer array whose sum is equal to a given number

If you want to learn more about the C language, you can check this course, Free Trial Available.

Get Your Free Trial

Sorting solution:

The sorting method is an optimized solution to find all pairs of an integer array whose sum is equal to a given number. Let’s see the logic to how to find all pairs of an integer array whose sum is equal to a given sum.

 

1. Create three intermediate variables left, right, and countPair.

2. Initialize the left, right, and countPair variables with 0, n-1, and  0 respectively.

3. Now sort the array using the qsort inbuilt function. You can use any other algorithm.

4. If arr[leftIndex] + arr[rightIndex] is equal to ‘sum’, then we found a pair. We increment the countPair variable with 1.

5. If arr [leftIndex] + arr[rightIndex] is less than ‘sum’, then increment leftIndex else decrement rightIndex.

6. Continue until leftIndex is less than rightIndex.

#include <stdio.h>
#include<stdlib.h>

//Calculate array size
#define ARRAY_SIZE(a)  sizeof(a)/sizeof(a[0])


//call back function
int compare(const void * a, const void * b)
{
    return ( *(int*)a - *(int*)b );
}

// Function to count pair in an array with a given sum using sorting
int findPair(int arr[], int n, int sum)
{
    int leftIndex = 0;
    int rightIndex = n - 1;
    int countPair = 0;

    //sort arr elements using qsort inbuilt function
    qsort( arr,n, sizeof(int), compare);


    // reduce the search space `arr[leftIndex…rightIndex]` at each iteration
    // of the loop till search space is exhausted
    while (leftIndex < rightIndex)
    {
        // sum found
        if (arr[leftIndex] + arr[rightIndex] == sum)
        {
            //increment count
            countPair++;
        }
        // increment `leftIndex` index if the total is less than the desired sum;
        // decrement `rightIndex` index if the total is more than the desired sum
        (arr[leftIndex] + arr[rightIndex] < sum)? leftIndex++: rightIndex--;
    }
    //return the count of pair
    return countPair;
}


int main()
{
    int arr[] = {1, 5, 7, -1, 5};
    int sum = 6;

    //find array size
    const int N = ARRAY_SIZE(arr);

    //get pairs in array
    const int pairCount = findPair(arr,N,sum);
    if(pairCount != 0)
    {
        printf("Count of pairs is %d\n\n",pairCount);
    }
    else
    {
        printf("Pair Not found");
    }

    return 0;
}
C program to find all pairs of an integer array whose sum is equal to a given number

Recommended Articles for you: