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)).
8 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–;
}
}
}
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–;
}
}
}
//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;
counttriad(array,0,len-1,count3,k);
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;
}
4 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.