Gearing Up for Destruction

Created: Jan 16, 2022

Last modified: Oct 10, 2026

#Math

#Optimization

TL, DR.

Gearing Up for Destruction
==========================

As Commander Lambda's personal assistant, you've been assigned the task of configuring the LAMBCHOP doomsday device's axial orientation gears. It should be pretty simple - just add gears to create the appropriate rotation ratio. But the problem is, due to the layout of the LAMBCHOP and the complicated system of beams and pipes supporting it, the pegs that will support the gears are fixed in place.

The LAMBCHOP's engineers have given you lists identifying the placement of groups of pegs along various support beams. You need to place a gear on each peg (otherwise the gears will collide with unoccupied pegs). The engineers have plenty of gears in all different sizes stocked up, so you can choose gears of any size, from a radius of 1 on up. Your goal is to build a system where the last gear rotates at twice the rate (in revolutions per minute, or rpm) of the first gear, no matter the direction. Each gear (except the last) touches and turns the gear on the next peg to the right.

Given a list of distinct positive integers named pegs representing the location of each peg along the support beam, write a function answer(pegs) which, if there is a solution, returns a list of two positive integers a and b representing the numerator and denominator of the first gear's radius in its simplest form in order to achieve the goal above, such that radius = a/b. The ratio a/b should be greater than or equal to 1. Not all support configurations will necessarily be capable of creating the proper rotation ratio, so if the task is impossible, the function answer(pegs) should return the list [-1, -1].

For example, if the pegs are placed at [4, 30, 50], then the first gear could have a radius of 12, the second gear could have a radius of 14, and the last one a radius of 6. Thus, the last gear would rotate twice as fast as the first one. In this case, pegs would be [4, 30, 50] and answer(pegs) should return [12, 1].

The list pegs will be given sorted in ascending order and will contain at least 2 and no more than 20 distinct positive integers, all between 1 and 10000 inclusive.

Test cases
==========

-- Python cases --
Inputs:
	(int) pegs = [4, 30, 50]
Output:
	(int) (12, 1)

Inputs:
	(int) pegs = [4, 17, 50]
Output:
	(int) (-1, 1)

This time you're tuning the gears of Lambda's doomsday device. The pegs are already bolted to a beam, and you must put a gear on every single one. Each gear touches the next, and the goal is for the last gear to spin twice as fast as the first. You have to return the radius of the first gear as a fraction a/b, or [-1, -1] if it can't be done.

It sounds like a physics problem, but don't worry: you only need two facts about gears, and the rest is a neat little trick.

# Gears 101

Fact 1: when two gears touch, the small one spins faster. In fact, speed is inversely proportional to the radius: half the size means twice the speed. And in a chain of gears, only the first and the last ones matter for the overall ratio. So "the last one spins twice as fast" just means:

r_0 = 2 \, r_n

Fact 2: two touching gears fill the space between their pegs exactly, so their radii add up to that distance. Calling $d_i$ the gap between peg $i$ and the next one:

r_i + r_{i+1} = d_i

Gear chain: each pair of radii adds up to the gap between pegs

# Pick the first gear and the rest falls like dominoes

Look at Fact 2 again: once you know $r_0$, the second gear has no choice, $r_1 = d_0 - r_0$. And then the third has no choice either. Let's write a few:

\begin{align*} r_1 &= d_0 - r_0 \\ r_2 &= d_1 - d_0 + r_0 \\ r_3 &= d_2 - d_1 + d_0 - r_0 \end{align*}

See the pattern? Each radius is an alternating sum of gaps (call it $S$), plus or minus $r_0$, and the sign of $r_0$ flips at every step. Even better, you don't need to recompute the sum each time: the new one is just the current gap minus the previous sum, $S \leftarrow d - S$.

# Closing the loop

When we reach the last gear, we know two things:

The chain says: $r_n = S \pm r_0$

The goal says: $r_0 = 2 r_n$

Two equations, one unknown: we can solve it! Whether it's a plus or a minus depends only on how many pegs there are.

Odd number of pegs (the sign is +):

\begin{align*} r_n &= S + r_0 \\ r_0 &= 2S + 2r_0 \\ r_0 &= -2S \end{align*}

Even number of pegs (the sign is −):

\begin{align*} r_n &= S - r_0 \\ r_0 &= 2S - 2r_0 \\ 3r_0 &= 2S \quad\Rightarrow\quad r_0 = \frac{2S}{3} \end{align*}

That's where the 3 in the denominator comes from!

Let's check it with the example from the statement, pegs at [4, 30, 50]:

Gaps: $d_0 = 30 - 4 = 26$ and $d_1 = 50 - 30 = 20$.

Alternating sum: first $S = 26$, then $S = 20 - 26 = -6$.

First gear: three pegs is odd, so $r_0 = -2 \cdot (-6) = 12$.

The rest of the chain: $r_1 = 26 - 12 = 14$ and $r_2 = 20 - 14 = 6$.

And 6 is exactly half of 12, just like we wanted.

One pass over the pegs and we're done: that's O(n), no system of equations, no matrices.

# The catch: the answer has to make sense

The formula always spits out a number, but that doesn't mean you can build it. Every gear needs a radius of at least 1, so after finding $r_0$ you walk the chain once more and check each one. The second example, [4, 17, 50], gives $r_0 = -40$, a gear with a negative size, so the answer is [-1, -1].

For the math lovers: the general formula

With $n + 1$ pegs at $x_0 < x_1 < \dots < x_n$, the gaps are $d_i = x_{i+1} - x_i$ and the alternating sums are defined as:

S_0 = 0, \qquad S_{k+1} = d_k - S_k

By induction, every radius can be written in terms of the first one:

r_k = S_k + (-1)^k \, r_0

And plugging in $r_0 = 2 r_n$:

r_0 = \left\{ \begin{array}{ll} -2 \, S_n & \text{if } n \text{ is even (odd number of pegs)} \\ \dfrac{2 \, S_n}{3} & \text{if } n \text{ is odd (even number of pegs)} \end{array} \right.

A solution exists if and only if $r_k \geq 1$ for every $k$. If you write the system as a matrix and reduce it with Gaussian elimination you reach the same result; the chain just gets there without building the matrix.

# Build your own

Your turn to be the engineer. Change the number of pegs or move them around, and if there's a valid configuration, the gears will appear and start spinning. Hover over a gear to see its radius. Try putting two pegs too close together, or one gap much bigger than the rest, and see what happens.

Number of pegs

Peg 0

Peg 1

Peg 2

Peg 3

Peg 4

It works! The first gear needs a radius of 20/1, and the radii are 20, 10, 10, 10, 10.

# The code

Here's my Python solution. It follows the same steps:

The first loop computes the gaps and keeps the running alternating sum in last_delta_peg (that's the $S \leftarrow d - S$ from above). It saves every partial sum in delta_pegs for later.

Then it picks the formula depending on whether the number of pegs is even or odd. If $S$ is divisible by 3, the denominator cancels out and the fraction is already in its simplest form.

The last loop rebuilds the middle gears from the partial sums and returns [-1, -1] as soon as one is smaller than 1.

def solution(pegs):
    if len(pegs) > 20 or len(pegs) < 2:
        return [-1, -1]
    if pegs[0] < 1:
        return [-1, -1]
    last_delta_peg = 0
    delta_pegs = []
    for i in range(1, len(pegs)):
        if pegs[i] < 1:
            return [-1, -1]
        delta_peg = pegs[i] - pegs[i - 1]
        if delta_peg < 1:
            return [-1, -1]
        last_delta_peg = delta_peg - last_delta_peg
        delta_pegs.append(last_delta_peg)
    # Find last and the first gears
    if len(pegs) % 2 == 0:
        den = 3
        last_gear_value = last_delta_peg / 3.
        if last_delta_peg % 3 == 0:
            last_delta_peg = last_delta_peg / 3
            den = 1
    else:
        last_delta_peg = -1 * last_delta_peg
        last_gear_value = last_delta_peg
        den = 1
    # the last gear is half the first one, and it must also be >= 1
    if last_gear_value < 1:
        return [-1, -1]
    num = 2 * last_delta_peg
    # Check if any gear < 1
    r_n = 2
    for i in range(0, len(delta_pegs)-1):
        r = delta_pegs[i] - r_n * last_gear_value
        if r < 1:
            return [-1, -1]
        r_n = -r_n
    return [num, den]

# Wrapping up

At first sight this looks like a job for a full system of equations. But each equation only links two neighbors, and that structure lets everything collapse into a single loop. Before reaching for the heavy tools, it's always worth asking: what does each piece actually depend on?