0863MediumArrayBit Manipulation

Largest Shared Mask That Still Sorts

Tracked in this browser only

Trains the technique from

LeetCode 3644Maximum K to Sort a Permutation

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 n trays numbered 0 through n - 1, and nums is a permutation of those numbers giving the label on each tray.

A lifter is set to a whole number k. It may exchange the labels in two trays only when both of those labels carry every bit that k carries, that is when label & k == k for each of them. Exchanges may be made as often as wanted.

Return the largest k for which the lifter can bring the rack into increasing order, so that the label in every tray equals the tray's own number. At least one label starts out in the wrong tray.

Examples

Example 1

Input: nums = [0, 1, 2, 3, 5, 4]
Output: 4

The labels 5 and 4 are the ones in the wrong trays. Both carry the third bit, and 5 also carries the lowest bit while 4 does not, so the bits they share come to 4.

Example 2

Input: nums = [2, 3, 0, 1]
Output: 0

All four labels are in the wrong trays, and the label 0 carries no bits at all, so the bits shared by every misplaced label come to 0.

Example 3

Input: nums = [5, 4, 7, 6, 1, 0, 3, 2]
Output: 0

Every label is in the wrong tray, and the label 0 is among them, so no bit is shared by all of them.

Constraints

2 <= nums.length <= 10^5
0 <= nums[i] <= 99999
nums is a permutation of the numbers from 0 to nums.length - 1
At least one label starts in the wrong tray

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 largest_shared_mask(nums: list[int]) -> int:

Java

public int largestSharedMask(int[] nums)

The intended approach

Time O(n) for n trays: one pass.Space O(1).

Every label that starts in the wrong tray has to be exchanged at least once, so each of them must carry every bit of `k`. That caps `k` at the bitwise AND of exactly those labels, since a bit missing from any one of them can never be in `k`. Taking `k` to be that AND also works: all the misplaced labels then carry every bit of it, so any two of them may be exchanged, and free exchanges among a set of labels can realise any rearrangement of them. So the AND of the misplaced labels is both the ceiling and achievable.

Pythonentry point: largest_shared_mask

def largest_shared_mask(nums):
    shared = None
    for tray, label in enumerate(nums):
        if label == tray:
            continue
        shared = label if shared is None else (shared & label)
    return 0 if shared is None else shared

The obvious version

Try every candidate mask from the largest label downwards and, for each, check by explicit search whether the rack can be sorted: gather the labels the mask allows to move, and require that every misplaced label is among them. Makes no bitwise argument about which mask is best.

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_largest_shared_mask(nums):
    n = len(nums)
    top = 1
    while top <= max(nums):
        top *= 2
    for k in range(top - 1, -1, -1):
        movable = set()
        for label in nums:
            if label & k == k:
                movable.add(label)
        ok = True
        for tray in range(n):
            if nums[tray] != tray and nums[tray] not in movable:
                ok = False
                break
        if not ok:
            continue
        # the labels that must move can be rearranged freely among themselves
        need = sorted(nums[t] for t in range(n) if nums[t] != t)
        have = sorted(t for t in range(n) if nums[t] != t)
        if need == have:
            return k
    return 0

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