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;
}
Mohna
👍👌
Tushar
In the second approach how we return the index of numbers ??
Durgesh kumar
WHICH IS FASTER METHOD?
BRUTEFORCE OR HASHING METHOD…
ajay
Hash map method
lohith
#include
using namespace std;
int main() {
int n;
cin>>n;
int a[n];
for(int i=0;i>a[i];
}
int k;
cin>>k;
int i=0,j=n-1;
while(i<j){
if(a[i]+a[j]==k){
cout<<i<<" "<<j;
break;
}
else if(a[i]+a[j]<k){
i++;
}
else{
j–;
}
}
}
Kedareshwar Awasthi
def find_sum(my_list, target):
result = []
for i in my_list:
if target – i in my_list:
result.append((my_list.index(i),my_list.index(target-i)))
return result
print(find_sum([2,7,11,15], 9))
Kedareshwar Awasthi
#include
using namespace std;
int binarySearch(int arr[], int l, int r, int x){
int mid = l +(r-l)/2;
if(r >= l){
if (arr[mid] == x){
return mid;
}
else if (arr[mid]>x){
return binarySearch(arr,l,mid-1,x);
}else{
return binarySearch(arr,mid+1,r,x);
}
}
return -1;
}
int findPairs(int arr[], int array_len, int num){
int temp, hashTable[100]={0};
for(int i = 0;i=0 && hashTable[temp] == 1){
cout << binarySearch(arr,0,array_len-1,temp) << ", "<<i;
return 0;
}
hashTable[arr[i]]++;
}
}
int main(int argc, char** argv) {
int array[] = {0,7,15,2};
findPairs(array,4, 9);
return 0;
}
Aman negi
It can done using binary search
Suraj Kumbhar
I think 2 pointer approach would be way better… We can cut down the space complexity to constant space.
Random
import java.util.*;
public class test{
public static void main(String[] args) {
int []arr={1,1,11,15};
int target=12;
for(int i=0;i<arr.length&& arr[i]=0){
System.out.println(i+”,”+got);
break;
}
}
}
}