0833MediumArrayHash TableEnumeration

Longest Mirrored Power Run

Tracked in this browser only

Trains the technique from

LeetCode 3020Find the Maximum Number of Elements in Subset

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 test rig logs gain readings in readings. An engineer wants to pick a group of those readings, keeping no more copies of a value than the log holds, and lay the picked readings in a row.

The row has to be shaped like this. It opens on some reading. Each step towards the middle squares the reading before it. One reading sits alone in the middle, the largest in the row. After the middle the row descends through exactly the readings it climbed, in reverse, so it reads the same forwards and backwards. A row of a single reading is allowed, with that reading serving as its own middle.

Return the largest number of readings such a row can hold.

Examples

Example 1

Input: readings = [3, 9, 3, 81, 7]
Output: 3

Laying 3, 9, 3 gives a row that climbs from 3 to its square 9 and comes back down, and the log holds two copies of 3 and one of 9. That row holds three readings.

Example 2

Input: readings = [5, 6]
Output: 1

No value appears twice, so no row can climb. A single reading is a valid row, so the answer is 1.

Example 3

Input: readings = [2, 2, 4, 4, 16]
Output: 5

Laying 2, 4, 16, 4, 2 uses both copies of 2, both copies of 4 and the single 16 as the middle reading, so the row holds five readings.

Constraints

2 <= readings.length <= 10^5
1 <= readings[i] <= 10^9

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 longest_mirror_run(readings: list[int]) -> int:

Java

public int longestMirrorRun(int[] readings)

The intended approach

Time O(n log log M) for n readings up to M: one tally, then a short squaring climb per distinct value.Space O(n) for the tally.

Tally how many copies of each value the log holds. A row is fixed by its starting reading, so try each distinct value as the start. Every rung below the middle appears twice, so climb by squaring while the tally holds at least two copies, adding two each time, then cap the row with one copy of the next square if the log has one; if it does not, drop back to the last rung, which then serves as the middle. The value 1 squares to itself, so a row starting at 1 is all ones and needs an odd count, handled on its own. Squaring passes the value ceiling within a few steps, so each start costs logarithmic work.

Pythonentry point: longest_mirror_run

def longest_mirror_run(readings):
    tally = {}
    for value in readings:
        tally[value] = tally.get(value, 0) + 1

    # a run built on 1 is 1, 1, ..., 1 and must keep an odd count
    best = tally.get(1, 0)
    if best % 2 == 0:
        best = max(best - 1, 0)

    for seed in tally:
        if seed == 1:
            continue
        length = 0
        here = seed
        while tally.get(here, 0) >= 2:
            length += 2
            here = here * here
            if here > 10 ** 9:
                break
        if tally.get(here, 0) >= 1:
            length += 1
        else:
            length -= 1
        if length > best:
            best = length
    return best

The obvious version

For every distinct start and every half-length, build the row the definition describes, count how many copies of each value it needs, and check the log holds them. Keeps the largest row that fits, making no argument about where the climb must stop.

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_longest_mirror_run(readings):
    tally = {}
    for value in readings:
        tally[value] = tally.get(value, 0) + 1
    cap = len(readings)
    best = 1
    for seed in set(readings):
        for half in range(0, cap + 1):
            # the run is seed, seed^2, ..., seed^(2^(half-1)), peak, and back down
            chain = []
            here = seed
            fits = True
            for _ in range(half):
                chain.append(here)
                if here > 10 ** 18:
                    fits = False
                    break
                here = here * here
            if not fits:
                break
            run = chain + [here] + chain[::-1]
            need = {}
            for value in run:
                need[value] = need.get(value, 0) + 1
            if all(tally.get(value, 0) >= count for value, count in need.items()):
                if len(run) > best:
                    best = len(run)
            else:
                break
    return best

How this problem was checked

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