Solution Description:
This problem can be solved in 2 different ways.
Solution 1: Brute Force Technique
Explanation: In this technique, we shall be taking 2 loops. Outer Loop and Inner Loop.
Step 1: First take the first element of the outer loop and add it to every other element from the inner loop array. And check if the sum is equal to the “key”. If it matches we return from the loop.
Step 2: Else we go for the second element and add it to every other element of the inner loop.
We continue the above steps until we reach the end of the outer loop. If we get a match program will return 1 else, it will return 0.
Example:
Take the array [1,2,3,4] and “key” is 7.
Pass 1: 1 + 2 = 3 false 1 + 3 = 4 false 1 + 4 = 5 false
Pass 2: 2 + 3 = 5 false. 2 + 4 = 6 false.
Pass 3: 3 + 4 = 7 true.
Time Complexity:
Since the program is using 2 for loops, the time complexity will be O(n^2).
Solution in C language:
# include <stdio.h>
int checkSum(int arr[], int arr_size, int key)
{
int i = 0;
int j = 0;
int sum = 0;
for (int i = 0; i < arr_size; ++i)
{
for (int j = i+1 ; j < arr_size; ++j)
{
sum = arr[i] + arr[j];
if (sum == key)
{
return 1;
}
}
}
return 0;
}
int main()
{
int array[] = {1,2,3,4,5,6};
int key = 11;
int array_size = 6;
if(checkSum(array, array_size, key))
printf("Array has two elements with given key\n");
else
printf("Array doesn't have two elements with given sumkey\n");
return 0;
}
Output:
Array has two elements with given key
Solution 2: Hashing Technique
In this technique is useful when the range of the number is known. For our program we have taken it as 1000.
Explanation:
Take an empty hash table say hashTable[].
Then we check if hashTable[ key – array[i] ] is set, then we shall print the pairs,
Else we update the vavlue 1 to s[ array[i] ].
Hence the for loop will be:
for(i = 0; i < array_size; i++)
{
temp = key - array [i];
if (temp >= 0 && hashTable[temp] == 1)
printf("Elements are present");
s[ array[i] ] = 1;
}
Example:
Let us take the input [1, 2, 3, 4, 5] key is 9.
Pass 1: i = 0; temp = 9 - 1 = 8 if( 8 >= 0 && hashTable[8] == 1) false hashTable[ 1 ] = 1; Pass 2: i = 1; temp = 9 - 2 = 7 if( 7 >= 0 && hashTable[7] == 1) false hashTable[ 2 ] = 1; Pass 3: i = 2; temp = 9 - 3 = 6 if( 6 >= 0 && hashTable[6] == 1) false hashTable[ 3 ] = 1; Pass 4: i = 3; temp = 9 - 4 = 5 if( 5 >= 0 && hashTable[5] == 1) false hashTable[ 4 ] = 1; Pass 5: i = 4; temp = 9 - 5 = 4 if( 4 >= 0 && hashTable[4] == 1) true hashTable[ 5 ] = 1;
C program to implement the same:
# include <stdio.h>
#define MAX 100000
void checkPairs(int array[], int array_size, int key)
{
int i, temp;
int hashTable[MAX] = {0};
for(i = 0; i < array_size; i++)
{
temp = key - array [i];
if (temp >= 0 && hashTable[temp] == 1)
printf("Elements are present\n");
hashTable[ array[i] ] = 1;
}
}
int main()
{
int array[] = {1,2,3,4,5,6};
int key = 11;
int array_size = 6;
checkPairs(array, array_size, key);
return 0;
}
