Show problems as
Classic problem #1679MediumArrayHash TableTwo PointersSorting

Max Number of K-Sum Pairs

Real-world version: Pairing Crates Onto Pallets
Tracked in this browser only
Read Max Number of K-Sum Pairs on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A loading bay has crates on the floor; weights[i] is the weight of crate i in kilograms. A pallet is only accepted when it carries exactly target kilograms in exactly two crates.

One loading step chooses two crates still on the floor whose weights add up to target and moves both of them onto a pallet, out of reach of later steps. Return the largest number of loading steps that can be carried out.

Examples

Example 1

Input
weights = [1, 9, 3, 7, 5, 5], target = 10
Output
3

Load 1 with 9, then 3 with 7, then the two crates of 5. Each pallet carries exactly 10 kilograms in two crates, and the floor is empty, so 3 steps are done.

Example 2

Input
weights = [2, 2, 2, 2], target = 4
Output
2

Two crates of 2 make one pallet of 4, and the other two make a second. Each crate is used on one pallet only, so 2 steps are done.

Example 3

Input
weights = [1, 3, 3, 3], target = 4
Output
1

The crate of 1 pairs with a crate of 3 for a pallet of 4. The two crates of 3 still on the floor add up to 6, not 4, so no further step is possible and the answer is 1.

Constraints

  • 1 <= weights.length <= 10^5
  • 1 <= weights[i] <= 10^9
  • 1 <= target <= 10^9

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def max_operations(weights: list[int], target: int) -> int:
Java
public int maxOperations(int[] weights, int target)

More on the same topics