Consider the following problem: Suppose you have k nephews and d dollars in your
ID: 647687 • Letter: C
Question
Consider the following problem:
Suppose you have k nephews and d dollars in your pocket all of which you need to spend. Given a set of n toys with different prices, find whether there exists k gifts with total cost exactly d.
If k=2, is it possible to have an algorithm that runs in o(n2)? If not, how to prove this?
Consider the case k=2 and the prices are all nonnegative integers. In this case, we should have an O(nd) algorithm by iterating through the toys and remembering the prices we have already seen.
Is it possible to remember which numbers seen from a sequence of length n of integers between 1 and d in less than ?(nd) time? It seems like one could use binary representation of numbers to remember in nlogd time.
Explanation / Answer
Get the naive approach out of the way: We have a set of n candidate toys, out of which we need to select k such that the total cost is equal to d. Lets consider the most naive approach to check if k such toys: exhaustively consider all (nk) possible combinations of toys and for each such k-set check whether the total price is equal to d. But,
(nk)?nk
while for a given k-set, the total price is checked in O(k). Hence, the total running time for this naive procedure is
O(knk).
For k=2, this is clearly an O(n2) algorithm, but not o(n2).
Second approach. A second, relatively straightforward approach is to classify items in d bins according to their price (like a histogram, but well.. not exactly). Why is this useful? If our final pair contains an item of cost i (i.e., from bin i) then the second item must be from bin d?i.
Consider d bins labeled 1,