Problem:
Describe a Θ(n lg n)-time algorithm that, given a set S of n integers and another integer x,
determines whether or not there exist two elements in S whose sum is exactly x.
Solution:
Complexity: O(n log n)
Code:
Describe a Θ(n lg n)-time algorithm that, given a set S of n integers and another integer x,
determines whether or not there exist two elements in S whose sum is exactly x.
Solution:
- Merge sort the elements which will take O(n log n)
- then have two pointers one from beginning and another from end
- if sum of both the elements a[i]+a[j] < sum then i++
- else if sum of both the elements a[i]+a[j] > sum then j--
- else we found print those elements a[i] and a[j].
- complexity is O(n) in worst case.
- Alternatively, after merge sort, do binary search for tmp=Sum - a[i] in the array a[i+1 ... n]
- here for binary search complexity is O(log n), so still total worst case complexity is O(n log n)
Complexity: O(n log n)
Code:
