Four entries that hit the target

Scenario

A payments app settles a batch of transfers. Each amount is signed: money in is positive, and money out is negative. Amounts may repeat.

Reconciliation looks for groups of four amounts that add up to a target, such as the fee of a split payment. Two groups with the same four values count as the same combination, whichever transfers they come from. You are asked to count the distinct combinations of values.

Your task

Write count_quads(amounts, target).

amounts is the batch, in no particular order. Amounts may repeat.
A quadruple is four different positions. Its combination is the four values, ignoring order.
Return the number of distinct combinations of four values that come from some quadruple and add up to target.
Two quadruples with the same four values count once.

Examples

Example 1 (traced)#

text2 lines

Input:  amounts = [1, 0, -1, 0, -2, 2], target = 0
Output: 3

Sort the amounts: -2, -1, 0, 0, 1, 2. Fix the first two, then walk two pointers over the rest. Repeated values are skipped, so each combination is counted once.

First	Second	lo value	hi value	Total	What happens
-2	-1	0	2	-1	too low: lo moves up
-2	-1	0	2	-1	the second 0 is still too low: lo moves up
-2	-1	1	2	0	match: -2, -1, 1, 2. Count is 1
-2	0	0	2	0	match: -2, 0, 0, 2. Count is 2
-1	0	0	2	1	too high: hi moves down
-1	0	0	1	0	match: -1, 0, 0, 1. Count is 3

The other choices of first and second entries have no match. The answer is 3.

Example 2#

text2 lines

Input:  amounts = [2, 2, 2, 2, 2], target = 8
Output: 1

Every quadruple has the values 2, 2, 2, 2. They are one combination.

Example 3#

text2 lines

Input:  amounts = [1, 2, 3], target = 6
Output: 0

A quadruple needs four entries, and there are only three.

Constraints

1 ≤ amounts.length ≤ 400 (transfers in one batch)
-10^6 ≤ amounts[i] ≤ 10^6 (amounts in minor units)
-4 × 10^6 ≤ target ≤ 4 × 10^6

What does n ≤ 400 tell you?

Checking every set of four positions costs about n^4 ÷ 24 checks. At n = 400 that is 1.1 × 10^9: about 11 seconds at 10^8 operations a second. Fixing two entries and walking two pointers costs about n × n × n ÷ 6 steps, 11 million.

A total of four amounts is at most 4 × 10^6 in size, which fits in a 32-bit integer. So does the count of combinations.

Scenario

A payments app settles a batch of transfers. Each amount is signed: money in is positive, and money out is negative. Amounts may repeat.

Your task

Write count_quads(amounts, target).

amounts is the batch, in no particular order. Amounts may repeat.
A quadruple is four different positions. Its combination is the four values, ignoring order.
Return the number of distinct combinations of four values that come from some quadruple and add up to target.
Two quadruples with the same four values count once.

Examples

Example 1 (traced)#

text2 lines

Input:  amounts = [1, 0, -1, 0, -2, 2], target = 0
Output: 3

Sort the amounts: -2, -1, 0, 0, 1, 2. Fix the first two, then walk two pointers over the rest. Repeated values are skipped, so each combination is counted once.

First	Second	lo value	hi value	Total	What happens
-2	-1	0	2	-1	too low: lo moves up
-2	-1	0	2	-1	the second 0 is still too low: lo moves up
-2	-1	1	2	0	match: -2, -1, 1, 2. Count is 1
-2	0	0	2	0	match: -2, 0, 0, 2. Count is 2
-1	0	0	2	1	too high: hi moves down
-1	0	0	1	0	match: -1, 0, 0, 1. Count is 3

The other choices of first and second entries have no match. The answer is 3.

Example 2#

text2 lines

Input:  amounts = [2, 2, 2, 2, 2], target = 8
Output: 1

Every quadruple has the values 2, 2, 2, 2. They are one combination.

Example 3#

text2 lines

Input:  amounts = [1, 2, 3], target = 6
Output: 0

A quadruple needs four entries, and there are only three.

Constraints

1 ≤ amounts.length ≤ 400 (transfers in one batch)
-10^6 ≤ amounts[i] ≤ 10^6 (amounts in minor units)
-4 × 10^6 ≤ target ≤ 4 × 10^6

What does n ≤ 400 tell you?

A total of four amounts is at most 4 × 10^6 in size, which fits in a 32-bit integer. So does the count of combinations.