Two books for a gift card
You have been given a bookshop gift card for S tenge. The rules are strict: you may take exactly two different books, and their prices must add up to exactly S; no change is given, and you cannot pay extra. In how many ways can such a pair be chosen from the catalogue?
Books with the same price are still different books, and a pair of them counts. One book cannot be taken twice. Order does not matter: “first and second” and “second and first” are one pair.
Input
The first line holds the numbers n and S (1 ≤ n ≤ 200,000, 2 ≤ S ≤ 2·10⁹). The second holds the n prices of the books a₁, …, an (1 ≤ ai ≤ 10⁹).
Output
One number: the number of pairs i < j with ai + aj = S. Note that the answer may not fit in 32 bits.
Examples
Example 1
6 1000 200 800 500 500 300 700
3
Example 2
4 1000 500 500 500 100
3
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1500 ms
- Memory
- 256 MB
- Judging
- 9 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
Going over all pairs is n(n − 1)/2, almost twenty billion with n = 200,000. Too many. Look at one book: how many possible prices does its partner have?
2Hint 2
Exactly one: S − a. So for each book you only need to know how many books cost S − a. How can such a question be answered in O(1)?
3Hint 3
To avoid counting a pair twice or pairing a book with itself, compare each book only with those met before it.
4The idea
Go through the catalogue from left to right, keeping a hash table “price → how many books with this price have been passed”. For the next book with price a, each book already passed with price S − a gives exactly one new pair; add their number to the answer, and only then record the book itself in the table. Each pair i < j is counted once, at the moment j is reached.
5Walkthrough
Two lines in the loop: pairs += seen.get(s - a, 0), then seen[a] += 1. The order matters. If you record the book first and then ask about S − a, then with 2a = S the book finds itself.
Exactly this mistake sits in the “obvious” two-pass solution: first count all the prices, then add count[S − a] for each book and halve the sum. Halving honestly removes the double counting of pairs with different prices, but a book with price S/2 has been paired with itself. In the second example three books at 500 give 3 · 3 = 9, after halving 4, while there are really three pairs. This can be fixed by subtracting the self-pairs, but the one-pass solution simply does not let them appear.
Another way is to sort the prices and walk two pointers from the ends. It works in O(n log n) without a hash table, but equal prices need care: blocks of equal values have to be multiplied, and at a = S/2 you take combinations of the block two at a time.
5+Solution
6Complexity
One pass, two hash table accesses per book: O(n) on average. Memory is O(n) for the table of distinct prices.
7Common mistakes
- A book paired with itself. Recording the book in the table before asking about its partner, or counting all prices in advance. Caught already by the first example.
- A set instead of counts. Pairs of books with the same price are lost: a set remembers that a price occurred, but not how many times.
- Overflow. Twenty billion pairs do not fit in 32 bits. Go needs
int64(orinton a 64-bit machine); in Python there is nothing to think about. - A double loop. Correct, but on 200,000 books it will take minutes.