Arrays & Strings
Problem
Given an array with ‘n’ elements & a value ‘x’, find two elements in the array which sums to ‘x’.
Consider the array { 37, 19, 4, 87, 21 } & a target value 25.
Two elements wich sums to 25 are 4 & 21 .
Solution
Approach 1 :: Using Sort.
Sort the elements and starting checking from the beginning of the array for the required pair. See the implementation below [ O(n*(log n)) complexity if we use the best sorting algorithm ]
Approach 2 :: Using a hash map.
We will initialize a hash_map of a large size (s.t all elements of the array are within this range) with all 0s.
As we iterate over the given array from i = 0 … n-1,
we will set hash_map[target-arr[i]] = 1. If at any point of time, we find an already set index, then we have found the two elements.
See the implementation below [ O(n) time complexity ]
#include<iostream>
#include<algorithm>
#define MAX 100000
using namespace std;
/*************** Method 1(Using Sort) **********************
We are using the STL sort function since we are interested
in the actual logic and not the sort function implementation
************************************************************/
bool isPairPresent1(int arr[], int size, int target) {
int start, end;
// sort the array
sort(arr,arr+size);
start = 0;
end = size-1;
while(start < end) {
// start checking from the max and min values
if (arr[start] + arr[end] == target) {
return target;
}
else if (arr[start] + arr[end] < target) {
start++;
}
else {
end--;
}
}
return false;
}
/*************** Method 2(Using Hashmap) **********************
This implementation works for positive integers only
**************************************************************/
bool isPairPresent2(int arr[], int size, int target) {
int i, val;
bool hash_map[MAX] = {0}; //initialize hash map as 0
for(i = 0; i < size; i++) {
val = target - arr[i];
if(val >= 0 && hash_map[val] == 1) {
return true;
}
// set the hash index of the value
// this denotes 'value' is present in the array
// for e.g. if arr[i] = 5, hash_map[5] = 1
hash_map[arr[i]] = 1;
}
return false;
}
// main
int main() {
//int arr[] = {7,-8,57, 6, 10, -4};
int arr[] = {37,19,4,87,23};
int size = sizeof(arr)/sizeof(arr[0]);
int target = 23;
if (isPairPresent1(arr, size, target))
cout<<"\nArray has two elements which sums to "<<target;
else
cout<<"\nArray doesn't have a pair which sums to "<<target;
cout<<endl;
return 0;
}