0235HardArrayMathDynamic ProgrammingNumber TheoryEuclidean AlgorithmGreatest Common Divisor

Matched Gear Benches

Tracked in this browser only

Trains the technique from

LeetCode 3336Find the Number of Subsequences With Equal GCD

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 machine shop is dividing a crate of spare gears between two benches. gears[i] is the tooth count of the gear at position i.

A split sends every gear to exactly one of three places: bench one, bench two, or back into the crate. Both benches must end up with at least one gear.

A split is matched when the greatest common divisor of the tooth counts at bench one is equal to the greatest common divisor of the tooth counts at bench two.

Two splits are different whenever some position ends up in a different place, so gears that happen to share a tooth count are still told apart by their position, and the two benches are told apart from each other.

Return the number of matched splits. The count can be enormous, so return it modulo 10^9 + 7.

Examples

Example 1

Input: gears = [4, 6, 18, 24]
Output: 2

Bench one can take the gear with 6 teeth while bench two takes those with 18 and 24 teeth, leaving the 4-tooth gear in the crate: the divisors are 6 and gcd(18, 24) = 6. Handing those same two rosters to the opposite benches is the other matched split.

Example 2

Input: gears = [3, 3]
Output: 2

Each bench takes one of the two gears and both rosters have divisor 3. The two gears sit at different positions, so the two ways of dealing them out are separate splits.

Example 3

Input: gears = [2, 3]
Output: 0

Neither bench may be left empty, so one bench gets the 2-tooth gear and the other the 3-tooth gear; the divisors are 2 and 3, which are not equal.

Constraints

1 <= gears.length <= 200
1 <= gears[i] <= 200

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 matched_gear_splits(gears: list[int]) -> int:

Java

public int matchedGearSplits(int[] gears)

The intended approach

Time O(n * M^2), where M is the largest tooth countSpace O(M^2) for the table plus the two transposed copies

Sweep the gears while holding a table indexed by the running divisor at each bench, with 0 standing for a bench that is still empty. Each gear offers three moves from every live cell: crate (the cell keeps its count), bench one (the row index becomes gcd(row, tooth)) and bench two (the column index moves the same way). The bench-one move is a row-wise merge, and transposing the table lets the identical row-wise merge serve bench two. Counts are added exactly and reduced modulo 10^9 + 7 every 24 gears so they stay short, then the answer is the sum of the diagonal cells with a divisor above 0.

Pythonentry point: matched_gear_splits

def matched_gear_splits(gears):
    from math import gcd
    from operator import add
    MOD = 10 ** 9 + 7
    top = max(gears) + 1
    # table[g1][g2] = plans over the gears handled so far whose bench-one roster
    # has common divisor g1 and whose bench-two roster has common divisor g2,
    # with 0 standing for a bench that is still empty
    table = [[0] * top for _ in range(top)]
    table[0][0] = 1
    for handled, tooth in enumerate(gears, 1):
        step = [gcd(g, tooth) for g in range(top)]
        step[0] = tooth
        to_one = [[0] * top for _ in range(top)]
        for g1 in range(top):
            row = table[g1]
            if not any(row):
                continue
            to_one[step[g1]] = list(map(add, to_one[step[g1]], row))
        flipped = [list(col) for col in zip(*table)]
        to_two_flipped = [[0] * top for _ in range(top)]
        for g2 in range(top):
            row = flipped[g2]
            if not any(row):
                continue
            to_two_flipped[step[g2]] = list(map(add, to_two_flipped[step[g2]], row))
        to_two = [list(col) for col in zip(*to_two_flipped)]
        for g1 in range(top):
            table[g1] = list(map(add, table[g1], map(add, to_one[g1], to_two[g1])))
        if handled % 24 == 0:
            table = [[count % MOD for count in row] for row in table]
    return sum(table[g][g] for g in range(1, top)) % MOD

The obvious version

Enumerate all 3^n placements of the gears, compute both benches' divisors from scratch and count the placements that match. O(3^n * n).

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_matched_gear_splits(gears):
    from math import gcd
    from itertools import product
    MOD = 10 ** 9 + 7
    total = 0
    for plan in product((0, 1, 2), repeat=len(gears)):
        one = two = 0
        for index, where in enumerate(plan):
            if where == 1:
                one = gcd(one, gears[index])
            elif where == 2:
                two = gcd(two, gears[index])
        if one and two and one == two:
            total += 1
    return total % MOD

How this problem was checked

Reference solution executed against 13 test cases — 13 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