# $k$-gifts problem

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(n^2)$? 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 $\Omega(nd)$ time? It seems like one could use binary representation of numbers to remember in $n\log d$ time.

• Looks like homework? – Ryan Williams Mar 8 '15 at 22:36
• Looks like a special case of Subset Sum. – Raphael Mar 9 '15 at 8:16
• @RyanWilliams We don't care. – Raphael Mar 9 '15 at 8:17
• Great, another site for my TAs to monitor.... :) (Yes, I clicked the link and read the policy.) – Ryan Williams Mar 9 '15 at 8:21
• @RyanWilliams Not that it's really your business, but I've been preparing for an exam – Kuhndog Mar 10 '15 at 3:35

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 $\binom{n}{k}$ possible combinations of toys and for each such $k$-set check whether the total price is equal to $d$. But, $$\binom{n}{k} \le n^{k}$$ 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(k n^{k}).$$ For $k=2$, this is clearly an $O(n^{2})$ algorithm, but not $o(n^{2})$.

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, \dots, d$ with the $i$th bin corresponding to price $i$. This can be implemented as array with $d$ entries; access of entry $i$ costs $O(1)$. We scan the toys in $O(n)$ and place each toy in the suitable bin according to its price. In fact, we do not need to store all items. All we want is to store one item per bin (if one exists). As a special case, if $d$ is even, then in bin $d/2$ we store up to two items because two items of price $d/2$ can give total price $d$, but this does not affect the total complexity.

We scan the toys, and if a toy has price $i$ we access bin $i$ in $O(1)$, check if it is empty. If not, we can discard the item (because we already have an item of price $i$). If the bin is empty, we put that item in bin $i$. (As already mentioned, special care is taken for bin $d/2$ when $d$ is even.) This procedure is completed in $O(n)$.

Now, if we choose an item/toy from bin $i$, $1\le i < d$, then the second toy can only be in bin $d-i$. We can scan the bins as follows: check if bins $d-1$ and $1$ are empty. If both are not empty, then return the items stored in the two bins. If either or both are empty, continue by checking bins $2$ and $d-2$. This procedure can be completed in $O(d)$, and hence the entire procedure is completed in time $O(n+d)$. If $d = o(n^{2})$, then this algorithm satisfies our requirements. If not, we would have see how to improve it.

Third approach: A third approach is to sort the $n$ items according to their price from lowest to highest price. This takes $O(n \log n)$. Once we have the sorted array of items, we can start scanning from the first and last position (keeping two pointers, call them left and right). If the total price is greater than $d$, then we have to reduce it, so we move the right pointer one position to the left. If the price is less than $d$, we move the left pointer one position to the right. See where this is going? This procedure is dominated by the original sorting and is done in $O(n\log n) = o(n^{2})$. (edit I guess if $d$ is a free parameters of the problem, then possibly we need an additional $O(\log d)$ factor when we do the sorting... and if $d$ is too large, then this can still lead to problems.)

• Sorry, I needed a $o(n^2)$ algorithm, so $\lim \frac{n^2}{t(n)} = \infty$. – Kuhndog Mar 8 '15 at 21:04
• @Kuhndog ok, I will edit my answer.. – megas Mar 8 '15 at 21:07
• So, doesn't it take time to place an item in a bin? So that the initial scan takes place in more than linear time, it would be $O(nd)$ time? Please correct me if this is wrong. – Kuhndog Mar 8 '15 at 22:03
• @Kuhndog The histogram can be an array with $d$ entries, correct? Now we scan the toys. First toy has price $i$. The access to bin $i$ is $O(1)$. Checking if the bin is empty is $O(1)$. Note that for your problem you do not even need to store the histogram, i.e. you don't need to remember all items that go in bin $i$. It suffices to store only one item in each bin (or two items in bin $d/2$ if $d$ is even!). Because in the end you need just one item from each bin (or two items from bin $d/2$). I will edit the answer to note that. – megas Mar 8 '15 at 22:08
• The third approach works..but in array, accessing the $i$th element, is that constant? I was thinking $O(i)$, but I guess you're right, because you just add $i$ to the address of the array for example. Sorry for the confusion – Kuhndog Mar 8 '15 at 22:59

Here's a hint for $k=2$. Let $P = \{p_i : i\in [n]\}$ be the set of prices. In any solution $\{p_i,p_j\}$ with $p_i \le p_j$, you have $p_i \le d/2$ and $p_j\ge d/2$. Split $P$ into $A = \{ a\in P : a\le d/2\}$ and $B = \{b \in P : b > d/2\}$. If $A$ and $B$ are sorted, you can find if there is an $a\in A$ and $b\in B$ with $a + b = d$ in $O(n)$ time.