Given a number N and an array of numbers, determine if any pair of numbers in the array has a sum equal to N.

One approach is to sort the array and then do a binary search for the difference of N and the ith element for all i. Sorting is O(n log n) and searching for a pair for all elements is also O(n log n).

A faster approach is to maintain a set of visited elements and determine if the difference of N and the ith element exists in the set. This runs in a single pass of the array, or O(n) time.

bool pairSum(int n, Array numbers) { Set set if (numbers.length < 2) return false set.put(numbers[0]) for (i = 1; i < numbers.length; i++) { int m = numbers[i] int difference = n - m if (set.contains(difference)) return true set.put(m) } return false }