Interview Problem: Pair Hunt

CMPUT 275 - Tangible Computing
Interview Problem: Pair Hunt
Description
You are doing an internship at Walmart and your supervisor wants you to write a program
to find if there are pairs of products whose total cost equals a given amount T. The idea is
that they want to pair up distinct products to offer a “two for T” sale where for T dollars you
buy two distinct products whose individual prices add up to T. Your supervisor wants you
to do an initial feasibility analysis where you need to find a pair whose total cost equals the
given T. The trouble is that Walmart has a gazillion products, so your code needs to run fast.
Input
The input contains two lines, the first contains two space-separated integers n and T, where
2 ≤ n ≤ 250, 000 and 0 ≤ T ≤ 2 · 109
. Here, n is the number of distinct items sold and T is
the target price.
The next line contains n integers p1, p2, . . . , pn indicating the prices of the items. These
prices are distinct and satisfy 0 ≤ p1 < . . . < pn ≤ 109
.
Output
Print a single line, either “YES” or “NO”, responding to the question, “is there a pair (i, j)
with 1 ≤ i < j ≤ n such that pi + pj = T”.
Target Running Time
The target running time is O(n), and there is a very natural algorithm that can solve the
problem with this running time. However, we will consider any solution for full credit if the
running time bound is at least as good as O(n log n).
Sample Input 1
8 56
1 2 7 8 34 67 89 100
Sample Output 1
NO
Explanation: No two prices sum to 56.
Sample Input 2
8 56
1 2 7 28 34 67 89 100
Sample Output 2
NO
Explanation: While 28+28 = 56, one cannot pair up a product with itself.
Sample Input 3
4 13
3 4 5 8
Sample Output 3
YES
Explanation: 5+8 = 13.
Sample Input 4
8 11
3 4 5 6 7 8 10 11
Sample Output 4
YES
Explanation: All of 6+5, 3+8 and 7+4 sum to 11.
Grading Comments
Despite the fact this appears similar to a morning problem, it will be graded like a weekly
exercise. In particular:
• Style matters. Use appropriate comments, proper indentation, etc. Include a file
header. Consult the style guide on eClass.
• You must adhere exactly to the output specification: for example, if you output in the
wrong order or print extra whitespaces then you will receive a deduction. The test
centre must accept the output without any presentation error.
• You were only give a few test cases in the test centre files on eClass. We will test your
solution on additional test cases that adhere to the input specification.
• Partial credit may be obtained if your solution works on some inputs but not all inputs
in the described range.
• Adhere closely to the submission instructions for the weekly exercise. See the eClass
code submission link for details.