Show problems as
Classic problem #3020MediumArrayHash TableEnumeration

Find the Maximum Number of Elements in Subset

Real-world version: Longest Mirrored Power Run
Tracked in this browser only
Read Find the Maximum Number of Elements in Subset on LeetCode(opens in a new tab)

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

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

Python
def longest_mirror_run(readings: list[int]) -> int:
Java
public int longestMirrorRun(int[] readings)

More on the same topics