Distinct team totals · DSA Mastery

Scenario

A ride app gives every driver an experience score. Before a busy weekend, the dispatcher builds teams of two.

It takes the lowest score and the highest score among the drivers still waiting, and puts those two drivers in a team. It repeats until nobody is waiting.

You are asked to check how balanced the plan is. Balanced plans give many teams the same total, so you count the different team totals.

Your task

Write distinct_team_totals(scores).

scores[i] is the experience score of driver i. The number of drivers is even.
Repeat until nobody is left: take the driver with the lowest remaining score and the driver with the highest remaining score, and make them a team. If several drivers tie, any of them may be taken. The totals do not change.
A team's total is the sum of its two scores. Use the total, not the average, so every value is a whole number.
Return how many different team totals there are.

Examples

Example 1 (traced)#

text2 lines

Input:  scores = [2, 7, 4, 10, 3, 6]
Output: 2

Sort the scores: [2, 3, 4, 6, 7, 10]. Pointers lo and hi start at the two ends. At each step the pair at the pointers is a team. Then both pointers move in.

lo	hi	Lowest	Highest	Total	Different totals so far	Move
0	5	2	10	12	1	both pointers move in
1	4	3	7	10	2	both pointers move in
2	3	4	6	10	2	both pointers move in, the walk ends

The totals are 12, 10 and 10. There are two different ones.

Example 2#

text2 lines

Input:  scores = [5, 5]
Output: 1

Only one team exists, so there is one total: 10.

Example 3#

text2 lines

Input:  scores = [1, 2, 3, 10, 20, 50]
Output: 3

The teams are (1, 50), (2, 20) and (3, 10). Their totals are 51, 22 and 13. All three are different.

Constraints

2 ≤ scores.length ≤ 100,000, and the length is even (drivers in one weekend plan)
0 ≤ scores[i] ≤ 1,000,000 (experience points)

What does n ≤ 10^5 tell you?

Finding the lowest and highest score by scanning the whole list costs about n steps. Doing that for each of the n ÷ 2 teams costs about n × n ÷ 2 steps in total. At n = 100,000 that is about 5 × 10^9, roughly 50 seconds at 10^8 operations a second. Sorting once costs about n × log n, under 2 million steps.

A team total is at most 2 × 1,000,000 = 2,000,000. It fits in a 32-bit integer.

Scenario

A ride app gives every driver an experience score. Before a busy weekend, the dispatcher builds teams of two.

It takes the lowest score and the highest score among the drivers still waiting, and puts those two drivers in a team. It repeats until nobody is waiting.

You are asked to check how balanced the plan is. Balanced plans give many teams the same total, so you count the different team totals.

Your task

Write distinct_team_totals(scores).

scores[i] is the experience score of driver i. The number of drivers is even.
Repeat until nobody is left: take the driver with the lowest remaining score and the driver with the highest remaining score, and make them a team. If several drivers tie, any of them may be taken. The totals do not change.
A team's total is the sum of its two scores. Use the total, not the average, so every value is a whole number.
Return how many different team totals there are.

Examples

Example 1 (traced)#

text2 lines

Input:  scores = [2, 7, 4, 10, 3, 6]
Output: 2

Sort the scores: [2, 3, 4, 6, 7, 10]. Pointers lo and hi start at the two ends. At each step the pair at the pointers is a team. Then both pointers move in.

lo	hi	Lowest	Highest	Total	Different totals so far	Move
0	5	2	10	12	1	both pointers move in
1	4	3	7	10	2	both pointers move in
2	3	4	6	10	2	both pointers move in, the walk ends

The totals are 12, 10 and 10. There are two different ones.

Example 2#

text2 lines

Input:  scores = [5, 5]
Output: 1

Only one team exists, so there is one total: 10.

Example 3#

text2 lines

Input:  scores = [1, 2, 3, 10, 20, 50]
Output: 3

The teams are (1, 50), (2, 20) and (3, 10). Their totals are 51, 22 and 13. All three are different.

Constraints

2 ≤ scores.length ≤ 100,000, and the length is even (drivers in one weekend plan)
0 ≤ scores[i] ≤ 1,000,000 (experience points)

What does n ≤ 10^5 tell you?

A team total is at most 2 × 1,000,000 = 2,000,000. It fits in a 32-bit integer.