Show problems as
Classic problem #3644MediumArrayBit Manipulation

Maximum K to Sort a Permutation

Real-world version: Largest Shared Mask That Still Sorts
Tracked in this browser only
Read Maximum K to Sort a Permutation on LeetCode(opens in a new tab)

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

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

Python
def largest_shared_mask(nums: list[int]) -> int:
Java
public int largestSharedMask(int[] nums)

More on the same topics