1189HardArrayDynamic ProgrammingBit Manipulation

Two Trays of Punch Cards

Tracked in this browser only

Trains the technique from

LeetCode 3287Find the Maximum Sequence Value of Array

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 rack holds punch cards in a row, codes[i] being the code punched on the i-th card. Every code is below 128.

Take exactly 2 * pick cards off the rack, keeping the rack's order. The first pick cards you took go on the left tray and the last pick on the right tray.

The reading of such a choice is the bitwise OR of the left tray's codes, XOR the bitwise OR of the right tray's codes. Return the largest reading you can get.

Examples

Example 1

Input: codes = [1, 2, 4, 8], pick = 2
Output: 15

All four cards are taken, so the left tray ORs to 3 and the right tray to 12. Those share no bits, so the reading is 15.

Example 2

Input: codes = [127, 1, 1, 127], pick = 1
Output: 126

Putting a card punched 127 on one tray and a card punched 1 on the other leaves every bit set but the lowest, which is 126. No choice does better, since both trays would have to differ in all seven bits.

Example 3

Input: codes = [8, 1, 1, 4, 2], pick = 2
Output: 15

Skipping the third card puts 8 and 1 on the left tray for 9 and 4 and 2 on the right for 6, and 9 XOR 6 is 15. Taking four cards side by side never reaches that.

Constraints

2 <= codes.length <= 400
1 <= codes[i] <= 127
1 <= pick <= 200
2 * pick <= codes.length

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 max_value(codes: list[int], pick: int) -> int:

Java

public int maxValue(int[] codes, int pick)

The intended approach

Time O(n * pick * 128) for the two sweeps, then O(128 * 128) per cut.Space O(n * 128) for the reachable sets along the rack.

Every code is below `128`, so an OR of codes is one of only 128 values. That is the whole opening: rather than tracking choices, track which OR values are reachable. Fix the place where the left tray's cards stop and the right tray's cards begin. For a cut after position `i`, the left tray draws `pick` cards from the first `i` and the right tray draws `pick` from the rest, and the two draws never interfere. So work out, for every prefix, the set of ORs reachable by taking exactly `pick` of its cards, and the same for every suffix by running the rack backwards. Each set is a table over card count holding a 128-bit set of reachable ORs. Reading the rack card by card and walking the counts downward keeps each card used at most once: every OR already reachable with `j` cards becomes that OR combined with this card, reachable with `j + 1`. Then, for each cut, pair every reachable left OR with every reachable right OR and keep the largest XOR. Both sides hold at most 128 values, so a cut costs a bounded amount of work.

Pythonentry point: max_value

def max_value(codes, pick):
    n = len(codes)

    def reachable(order):
        out = [0] * (len(order) + 1)
        counts = [0] * (pick + 1)
        counts[0] = 1
        for i, code in enumerate(order):
            top = pick - 1
            if i < top:
                top = i
            for j in range(top, -1, -1):
                bits = counts[j]
                if not bits:
                    continue
                grown = 0
                value = 0
                while value < 128:
                    if bits >> value & 1:
                        grown |= 1 << (value | code)
                    value += 1
                counts[j + 1] |= grown
            out[i + 1] = counts[pick]
        return out

    ahead = reachable(codes)
    behind = reachable(codes[::-1])
    best = 0
    for i in range(pick, n - pick + 1):
        left = ahead[i]
        right = behind[n - i]
        if not left or not right:
            continue
        lefts = []
        value = 0
        while value < 128:
            if left >> value & 1:
                lefts.append(value)
            value += 1
        rights = []
        value = 0
        while value < 128:
            if right >> value & 1:
                rights.append(value)
            value += 1
        for a in lefts:
            for b in rights:
                if a ^ b > best:
                    best = a ^ b
    return best

The obvious version

Take every choice there is. Run over all ways of picking `2 * pick` positions in order, OR the first `pick` codes into one tray and the rest into the other, XOR the two and keep the largest. Costs one pass per choice, of which there are as many as there are ways to choose the positions.

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_max_value(codes, pick):
    from itertools import combinations
    best = 0
    for spots in combinations(range(len(codes)), 2 * pick):
        left = 0
        for at in spots[:pick]:
            left |= codes[at]
        right = 0
        for at in spots[pick:]:
            right |= codes[at]
        if left ^ right > best:
            best = left ^ right
    return best

How this problem was checked

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