FIND A PAIR IN ARRAY WHOSE SUM IS EQUAL TO GIVEN NUMBER
Given an Array A and a number X ,find all pair (a,b) in A such that a+b=X.
A=1 2 10 6 9 11 5
X=8
maximum number of pair can be possible is nc2
Approach 1:
we can find out all possible pairs using these n elements ,then number of possible pairs from these n elements will be nc2,so out of all these pair we can take each pair
one by one and we can find out the sum ,and we will check whether the sum is equal to X or not
and for this the time complexity is going to be O(n²)
nc2= n(n-1)/2 these many pairs we are going to get ,and for every pair we have to test whether that pair is equal to X or not and it is going to takeO(1) time
Approach 2:
A= 1 20 5 6 9 2 10
now i want to find out a pair whose sum is equal to 8
so now i will take each element from array one by one ,
so i take 1 ,since 1 has to be added with some number in order to get sum as 8 ,and what that number should be ?,so that number will be 8–1 =7 ,so in this entire array we can search and find whether that number 7 is present or not ,
now what happens is ,for every number you have to search its corresponding number then time complexity will be O(n²)
when i pick element 1 ,then i have to search entire n-1 elements
when i pick element 20 ,then also i have to search entire n-1 elements in order to find corresponding element
Approach 3:
so using hash the timecomplexity is going to be O(n)
now lets analyze:
take a hash table ,and into this hash table we will push all the elements from array A, and for a given number 1 we will check whether corresponding element is present in hash or not.
let say : 8–1 =7 ,so i will check whether 7 is present in hash or not, and searching in hash take O(1) time
there are n elements and for each number i will find its corresponding number and then i will search in hash whether that corresponding element is present in hash or not.
O(n)*O(1)=O(n)
steps:
insert all element in hash will take O(n) time
for each element a search corresponding element b in hash O(n) time
space complexity:
since all the elements shoulddd be present in hash therefore the space complexity will be O(n):
IMPLEMENTATION OF PRINTING ALL PAIRS IN AN ARRAY WHOSE SUM IS X:
Depending on the size of array ,i am declaring hash table of that size ,which means if the maximum no of elements present in array is 100 ,then the hash table size
will also be 100 ..
#define MAX 10
(in C the problem is ,you cannot declare arrays dynamically ,you are suppose to specify the size of an array statically ,that is why we are using MAX .)
Arr= 1 4 3 3 5 2 6
ind=0 1 2 3 4 5 6
sum=9
size=7
void findpairs(int *arr,int size ,int sum)
{
int index ,temp;
int hash[MAX]={0} ,the hash table initially initailized to 0
for(index=0; index < size ;index++)
{
temp=sum-arr[index] # 9–1=8 now i will search whether 8 is present in hash or not
if(temp >=0 && hash[temp]==1) # temp>=0 because we are considering only +ve no in array
printf(“pair with given sum %d is””(%d,%d)\n,sum ,arr[index],temp);
hash[arr[index]==1;
}
}
HASH
0 0
1 0
2 0
3 0
4 0
5 0
6 0
7 0
8 0
9 0