The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as
well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. Donald E. Knuth

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

Back | Next

All problems on Arrays and Strings
* Reverse an array in place
* Sort an array of 0s and 1s
* Sort an array of 0s, 1s and 2s
* Print all the maxima elements in the array
* Check if two strings are anagrams
* Find the duplicate array elements
* Find the minimum element in a sorted and rotated array
* Remove all duplicate characters in a string
* Find two array elements which sum upto a target value
* Find the median of two sorted arrays
* Find if a sub-array of consecutive elements of size p exists which sum upto a target value
* Find the maximum difference between two elements in an array s.t larger element appears after the smaller element in the array
* Find the largest sum contiguous subarray
* Find the smallest positive element missing in the given array of size n consisting of both positive & negative integers
* Given an array of n elements, find max( j - i ) s.t arr(j) > arr(i)