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; }