Remove Pairs With a Given Sum

Medium

You are given an array of positive integers values and an integer target. In one move you pick two elements of the array (at different positions) whose sum equals target and remove both of them. Return the largest number of moves you can make.

Example 1

values=[2, 7, 4, 5, 3, 6], target=9 → 3

Remove 2 and 7, then 4 and 5, then 3 and 6: three moves, and the array is empty.

Example 2

values=[4, 4, 4, 1], target=8 → 1

Two of the 4s form a pair; the third 4 has no partner left, and 1 adds up to 8 with nothing.

Example 3

values=[10], target=10 → 0

Constraints

1 ≤ len(values) ≤ 10⁵
1 ≤ values[i] ≤ 10⁹
1 ≤ target ≤ 2 · 10⁹

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Hash Table Two Pointers Sorting

Similar problems

A Subsequence of One Word Only Medium Pairs With a Fixed Gap Medium Triples Hitting the Target Medium Word Growth Chain Medium Balanced Doubles Pairs Medium

Input

values=[2, 7, 4, 5, 3, 6], target=9

Expected

Run checks the first 3 tests in your browser. Submit checks all 69 tests on the server, hidden ones included.