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
If you want to learn more about the C language, you can check this course, Free Trial Available.
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;
}
Recommended Articles for you:
- Best gift for programmers.
- Best electronic kits for programmers.
- C program to find the Median of two sorted arrays of different sizes.
- C Program to find first and last position of element in sorted array
- Write C program to find the missing number in a given integer array of 1 to n
- C program to find the most popular element in an array
- Find the largest and smallest element in an array using C programming.
- C program to find even occurring elements in an array of limited range
- Find sum of all sub-array of a given array.
- C program to segregate even and odd numbers
- Find an element in array such that sum of left array is equal to sum of right array.
- C Program to find the count of even and odd elements in the array.
- Write C program to find the sum of array elements.
- C program to find odd occurring elements in an array of limited range
- Find the sum of array elements using recursion
- C Program to reverse the elements of an array
- C Program to find the maximum and minimum element in the array
- Calculate size of an array in without using sizeof in C
- How to create a dynamic array in C?
- How to access 2d array in C?
- Dangling, Void, Null and Wild Pointers
One comment