# Algorithm: Given an array, find all the pairs of elements whose sum is k.

algorithm for:-----

Given an array, find all the pairs of elements whose sum is k.

1 Like

also for
Given an array, find a sub-array in which all pairs have their sum greater than k.

For the original problem here is very simple `O(N * log N)` solution using STL map.

Put the array in map:

```map < int, int > cnt;
for (int i = 0; i < n; ++i) {
cnt[a[i]]++;
}
```

Then iterate over map and for the given value `val` add to the answer `cnt[val] * cnt[k - val]` if `val < k - val` and add `cnt[val] * (cnt[val] - 1) / 2` if `val == k - val`, since from the set containing only elements `k / 2` the number of pairs is the (cnt choose 2) number:

```long long ans = 0; // long long since for n up to 100000, the answer could not fit in int
for(auto &pair : cnt) // C++11 style
{
val = pair.first;
// use long long cast since this product can overflow
if (val < k-val) {
ans += (long long)cnt[val] * cnt[k - val];
} else if (val == k-val)
can += (long long)cnt[val] * (cnt[val] - 1) / 2;
}
```

`ans` is now the final answer.

The same can be made without map. You need to sort the array, create an array of pairs `(val, cnt)` like map from the previous solution, and then make the last loop either using binary search for finding `k - val` or using method if two pointers.

For the second problem you should clarify what is sub-array (contiguous or any sub-sequence), and what means `find sub-array` (just find any sub-array or with maximal size or find all such sub-arrays (their number)).

9 Likes

if by the second problem you mean “given a set of integers, is there a non-empty subset whose sum is S ?”, it’s a very well known problem called the Subset sum problem, and you can find information on wikipedia. Hope it helps.

2 Likes

int main(void)
{
int arr [10] = {1,2,3,4,5,6,7,8,9,0};
findpair(arr, 10, 7);
}
void findpair(int arr[], int len, int sum)
{
std::sort(arr, arr+len);
int i = 0;
int j = len -1;
while( i < j){
while((arr[i] + arr[j]) <= sum && i < j)
{
if((arr[i] + arr[j]) == sum)
cout << “(” << arr[i] << “,” << arr[j] << “)” << endl;
i++;
}
j–;
while((arr[i] + arr[j]) >= sum && i < j)
{
if((arr[i] + arr[j]) == sum)
cout << “(” << arr[i] << “,” << arr[j] << “)” << endl;
j–;
}
}
}

2 Likes

It’s not working well - http://ideone.com/EeGits

1 Like

int main(void)
{
int arr [10] = {1,2,3,4,5,6,7,8,9,0};
findpair(arr, 10, 7);
}
void findpair(int arr[], int len, int sum)
{
std::sort(arr, arr+len);
int i = 0;
int j = len -1;
while( i < j){
while((arr[i] + arr[j]) <= sum && i < j)
{
if((arr[i] + arr[j]) == sum)
cout << “(” << arr[i] << “,” << arr[j] << “)” << endl;
i++;
}
j–;
while((arr[i] + arr[j]) >= sum && i < j)
{
if((arr[i] + arr[j]) == sum)
cout << “(” << arr[i] << “,” << arr[j] << “)” << endl;
j–;
}
}
}

why are you adding that not working code here? see @dreamwarrior12’s post and counter example…

//finding no. of pairs of numbers accounting to a sum = k in O(n) and triads in O(n^2)

#include
using namespace std;

void countpair(int *array,int i,int len,int &count2 , int k)
{
int j=len;
count2=0;

``````while(i<j)
{
if(array[i]+array[j] == k)
{
if(i==0 && j==len )
{
count2++;
cout<<array[i]<<" "<<array[j]<<endl;
i++;
j--;
continue;

}
else
{
if(array[i]==array[i-1] && array[j]==array[j+1])
{
i++;
j--;
continue;
}
count2++;
cout<<array[i]<<" "<<array[j]<<endl;
i++;
j--;
continue;
}

}

if(array[i]+array[j] > k)
{
j--;
continue;
}

if(array[i]+array[j] < k)
{
i++;
continue;
}
}
``````

}

void counttriad(int *array,int i,int len,int &count3,int k)
{
int count2=0;
while(i<len)
{
if(i!=0)
{
if(array[i]==array[i-1])
{
i++;
continue;
}
}
count2=0;
countpair(array,i+1,len,count2,k-array[i]);//fixing that the value at that index
//and searching for the concerned pair in th e right part of the array
count3+=count2;
i++;

``````    if(count2!=0)
cout<<array[i]<<endl;

}
``````

}
int main()
{
int count2=0,count3=0;
int array[]={1,1,2,2,3,3,6,7,7,8,8,9,9,10,10,11,11};
int len=sizeof(array)/sizeof(int);

``````int k=12;
countpair(array,0,len-1,count2,k);
//cout<<endl<<endl<<count2<<endl<<endl;
cout<<endl<<endl<<count3<<endl<<endl;
return 0;
``````

}

1 Like

Find a pair of elements from an array whose sum equals a given number
Q.) Find a pair of elements from an array whose sum equals a given number (a,b)
enter code here

#include<stdio.h>
#include
using namespace std;
int main()
{
int num, X,i,ub,lb,search_num,mid,flag;

``````printf("enter the size of array=");

scanf("%d",&num);
scanf("%d",&X);
int arr[num];
for(i=0;i<num;i++)
scanf("%d",&arr[i]);
sort(arr,arr+num);
for(i=0;i<num;i++)
{
//binary search of search_num//
search_num=X-arr[i];
lb=0,ub=num-1,flag=0;
if(search_num>0)
{
while(lb<=ub)
{
mid=(lb+ub)/2;
if(arr[mid]==search_num)
{
flag=1;
break;
}
else if(arr[mid]>search_num)
ub=mid-1;
else
lb=mid+1;
}
}
if(flag==1&&mid!=i){
printf("(%d,%d)\n",arr[i],arr[mid]);
num=num-1; //decreasig the size of the array to stop reapeating ans like (1,11) (11,1)//
}
}
return 0;
``````

}

6 Likes

We can first sort the given array and using two pointers front and end,we can find all that pairs which add to a given number. Heapsort will take O(lgn) time and traversing the sorted array will take O(n) time.

//array should be sorted

``````i=0;
j=n-1;//array length-1
count=0;

while(i<j)
{
if(a[i]+a[j]==s)
{
printf("a[%d]+a[%d]=%d\n",i,j,a[i]+a[j]);
i++;
j--;
count++;
}
else if(a[i]+a[j]<s)
{
i++;
}
else
{
j--;
}
}
printf("Total number of pairs=%d",count);``````
1 Like

this is the implementation of O(n*lg n) using binary search implementation inside a loop.

``````#include <iostream>

using namespace std;

bool *inMemory;

int pairSum(int arr[], int n, int k)
{
int count = 0;

if(n==0)
return count;
for (int i = 0; i < n; ++i)
{
int start = 0;
int end = n-1;
while(start <= end)
{
int mid = start + (end-start)/2;
if(i == mid)
break;
else if((arr[i] + arr[mid]) == k && !inMemory[i] && !inMemory[mid])
{
count++;
inMemory[i] = true;
inMemory[mid] = true;
}
else if(arr[i] + arr[mid] >= k)
{
end = mid-1;
}
else
start = mid+1;
}
}
return count;
}

int main()
{
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
inMemory = new bool[10];
for (int i = 0; i < 10; ++i)
{
inMemory[i] = false;
}
cout << pairSum(arr, 10, 11) << endl;
return 0;
}``````

i think you should use the simple approach :-
suppose the input array is ARRAY and the given k is K;
actually there are two approaches first if the value of n is less than 10^6 then simple use count sort
or another approach is sort the array and use binary search for the given element . in this if the order of pair matters then go to every distinct element and use binary search with some constraints … it is ur home work

@anton_lunyov , why didn’t you use an unordered_map (C++ 11) instead of std::map ? What I meant by unordered_map is just a hash table… which could bring the complexity to O(n) …
Cant this problem be solved in O(n) ?Am i missing anything here, Pls reply…

Of course using hash table the complexity could be reduced to O(N) but C++11 is not always available on the online judges.

I am not stressing on the unordered_map, though. You suggested a solution without using map ,where you mentioned binary search. I thought, you should have atleast mentioned O(n) using a hash array - int hash[100000] to maintain the counts.

//