I was going through Introduction to algorithm, where I came across ex 2.3-7.

after much thought on it, I realised that the brute force algorithm takes O(nlogn):

bool exactSum(int arr[], const int &length, const int &value) {
  bool isExact = false;
  for(unsigned i = 0; i < length - 1;   i) {
    for(unsigned j = i   1; j < length;   j) {
      if(arr[i]   arr[j] == value) {
         isExact = true;
         break;
      }
    }
  }

  return isExact;
}

you see, there are only nlogn checks. am I wrong?

CodePudding user response：

The algorithm you described takes O(n^2) time complexity because for the worst case, there are n*(n-1)/2 comparisons.

All credits to @Shridhar R Kulkarni who pointed out that this problem can be solved even without sorting.

In such case, you will need to make use of hash map. Store the elements of the array and their respective count in the hashmap. Now, iterate the array elements. Let's say you are at index i. Just check if (value - are[i]) is present in the hashmap.

Time complexity = O(n).

Special Case

When arr[i] is equal to the value - arr[i], check if the count of the element arr[i] is greater than 1 for a pair to exist.

Credits for special case - @Dillon Davis.

CodePudding user response：

Answer posted by @Deepak is good enough for this post. However, you can simplify even more. The dictionary approach takes two iterations and extra conditional handling for case where a b = value and a = b. Instead you can do it in a single iteration and practically lesser space by using unordered set.

Psuedocode:

for element in array:
    if value - element in unordered_set:
        return true
    unordered_set.add(element)
return false

Time complexity: O(n)
Space complexity: O(n)

Using the same logic as above, you can make dictionary/hashmap work with single iteration to avoid an additional iteration to get the counts.