Show problems as
Classic problem #3867MediumArrayMathTwo PointersSortingSimulationNumber Theory

Sum of GCD of Formed Pairs

Real-world version: Total Mesh Cycle of the Gear Bin
Tracked in this browser only
Read Sum of GCD of Formed Pairs on LeetCode(opens in a new tab)

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

A gearbox shop keeps a bin of gear blanks. Blank i has been cut with teeth[i] teeth.

The shop empties the bin in rounds. In each round it takes the blank with the fewest teeth still in the bin and the blank with the most teeth still in the bin, meshes those two into a pair, and removes both from the bin. Rounds continue while at least two blanks remain. If the bin started with an odd number of blanks, one blank is left over at the end; it has no partner and contributes nothing.

Two blanks that carry the same number of teeth are interchangeable, so it never matters which of them a round picks.

The mesh cycle of a pair is the greatest common divisor of the two teeth counts.

Return the sum of the mesh cycles of all the pairs formed.

Examples

Example 1

Input
teeth = [6, 30, 10, 15]
Output
11

The first round meshes 6 with 30, whose greatest common divisor is 6. The second round meshes 10 with 15, whose greatest common divisor is 5. The sum is 11.

Example 2

Input
teeth = [840, 630, 420, 210, 105]
Output
315

Round one meshes 105 with 840 for 105, round two meshes 210 with 630 for 210, and 420 is left over with no partner. The sum is 315.

Example 3

Input
teeth = [55]
Output
0

One blank cannot fill a round, so no pair is ever formed and the sum is 0.

Constraints

  • 1 <= teeth.length <= 10^5
  • 1 <= teeth[i] <= 10^9
  • The total can reach 5 * 10^13, so it does not always fit in a signed 32-bit integer.

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 total_mesh_cycle(teeth: list[int]) -> int:
Java
public long totalMeshCycle(int[] teeth)

More on the same topics