0799MediumArrayMathTwo PointersSortingSimulationNumber Theory

Total Mesh Cycle of the Gear Bin

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def total_mesh_cycle(teeth: list[int]) -> int:

Java

public long totalMeshCycle(int[] teeth)

The intended approach

Time O(n log n + n log V) for n blanks and largest count V: the sort dominates, and each of the n/2 rounds runs one Euclid loop of O(log V) steps.Space O(n) for the sorted copy of the teeth counts.

Sorting the teeth counts once puts the fewest at the front and the most at the back, so the rounds are exactly a pair of pointers walking inward from the two ends of the sorted list. Each step adds the greatest common divisor of the two counts, found by Euclid's remainder loop, and the pointers meet in the middle, leaving the odd blank untouched.

Pythonentry point: total_mesh_cycle

def total_mesh_cycle(teeth):
    def common(a, b):
        # Euclid, by remainder
        while b:
            a, b = b, a % b
        return a

    order = sorted(teeth)
    low = 0
    high = len(order) - 1
    total = 0
    # two pointers walking inward: fewest teeth meets most teeth, round by round
    while low < high:
        total += common(order[low], order[high])
        low += 1
        high -= 1
    return total

The obvious version

Simulate the bin literally as a list: each round scans it for the smallest count, removes that blank, scans the rest for the largest count, removes that one too, and then works out the pair's greatest common divisor by factorising both counts with trial division and multiplying the shared prime powers. No sorting and no Euclid.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_total_mesh_cycle(teeth):
    def factor(x):
        parts = {}
        d = 2
        while d * d <= x:
            while x % d == 0:
                parts[d] = parts.get(d, 0) + 1
                x //= d
            d += 1
        if x > 1:
            parts[x] = parts.get(x, 0) + 1
        return parts

    bin_ = list(teeth)
    total = 0
    while len(bin_) >= 2:
        low = min(bin_)
        bin_.remove(low)
        high = max(bin_)
        bin_.remove(high)
        fa = factor(low)
        fb = factor(high)
        shared = 1
        for p in fa:
            if p in fb:
                shared *= p ** min(fa[p], fb[p])
        total += shared
    return total

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in