Most bundles that hit the price

Scenario

A shop app runs a bundle deal: pick any two different items, and together they cost one fixed bundle price.

A price only fits the deal if the two item prices add up to exactly that bundle price. Each item can go in at most one bundle, because a customer buys it once.

You are asked to find how many bundles the shop can make at most.

Your task

Write most_bundles(prices, target).

prices[i] is the price of item i, in minor units. target is the bundle price.
A bundle is two different items, i and j, with prices[i] + prices[j] == target. Two items may have the same price.
Each item goes in at most one bundle.
Return the largest number of bundles.

Examples

Example 1 (traced)#

text2 lines

Input:  prices = [4, 9, 2, 5, 7, 2, 8], target = 11
Output: 2

Sort the prices: [2, 2, 4, 5, 7, 8, 9]. Pointer lo starts at the cheapest item and hi at the dearest. At each step add the two prices and compare the total with the target.

lo	hi	Prices	Total	Bundles after	Move
0	6	2 and 9	11	1	equal to the target: count a bundle, lo becomes 1, hi becomes 5
1	5	2 and 8	10	1	too small: lo becomes 2
2	5	4 and 8	12	1	too large: hi becomes 4
2	4	4 and 7	11	2	equal to the target: count a bundle, lo becomes 3, hi becomes 3

The pointers meet, so the walk ends. The price 5 is left without a partner.

Example 2#

text2 lines

Input:  prices = [5, 5, 5], target = 10
Output: 1

Two of the three items make a bundle. The third has no second item to join, and an item cannot join itself.

Example 3#

text2 lines

Input:  prices = [1, 2, 3], target = 100
Output: 0

No two prices reach 100, so no bundle exists.

Constraints

1 ≤ prices.length ≤ 100,000 (items in the deal)
1 ≤ prices[i] ≤ 10,000,000 (minor units)
1 ≤ target ≤ 10,000,000 (minor units)

What does n ≤ 10^5 tell you?

Looking for a partner by scanning the list for every item costs about n × n ÷ 2 steps. At n = 100,000 that is about 5 × 10^9, roughly 50 seconds at 10^8 operations a second. Sorting costs about n × log n, under 2 million steps, and the walk after it makes at most 100,000 steps.

Two prices add up to at most 20,000,000, which fits easily in a 32-bit integer. The answer is at most 50,000.

Scenario

A shop app runs a bundle deal: pick any two different items, and together they cost one fixed bundle price.

A price only fits the deal if the two item prices add up to exactly that bundle price. Each item can go in at most one bundle, because a customer buys it once.

You are asked to find how many bundles the shop can make at most.

Your task

Write most_bundles(prices, target).

prices[i] is the price of item i, in minor units. target is the bundle price.
A bundle is two different items, i and j, with prices[i] + prices[j] == target. Two items may have the same price.
Each item goes in at most one bundle.
Return the largest number of bundles.

Examples

Example 1 (traced)#

text2 lines

Input:  prices = [4, 9, 2, 5, 7, 2, 8], target = 11
Output: 2

Sort the prices: [2, 2, 4, 5, 7, 8, 9]. Pointer lo starts at the cheapest item and hi at the dearest. At each step add the two prices and compare the total with the target.

lo	hi	Prices	Total	Bundles after	Move
0	6	2 and 9	11	1	equal to the target: count a bundle, lo becomes 1, hi becomes 5
1	5	2 and 8	10	1	too small: lo becomes 2
2	5	4 and 8	12	1	too large: hi becomes 4
2	4	4 and 7	11	2	equal to the target: count a bundle, lo becomes 3, hi becomes 3

The pointers meet, so the walk ends. The price 5 is left without a partner.

Example 2#

text2 lines

Input:  prices = [5, 5, 5], target = 10
Output: 1

Two of the three items make a bundle. The third has no second item to join, and an item cannot join itself.

Example 3#

text2 lines

Input:  prices = [1, 2, 3], target = 100
Output: 0

No two prices reach 100, so no bundle exists.

Constraints

1 ≤ prices.length ≤ 100,000 (items in the deal)
1 ≤ prices[i] ≤ 10,000,000 (minor units)
1 ≤ target ≤ 10,000,000 (minor units)

What does n ≤ 10^5 tell you?

Two prices add up to at most 20,000,000, which fits easily in a 32-bit integer. The answer is at most 50,000.