3644. Maximum K to Sort a Permutation

1. Description

The array nums has length n and contains each integer from 0 through n - 1 exactly once.
Choose a fixed non-negative integer k. You may exchange two elements only when their bitwise AND equals k, and may perform any number of such exchanges.
Find the largest k for which these exchanges can arrange nums in non-decreasing order. For an array that is already sorted, return 0.

2. Example

Example 1

Input: nums = [0,3,2,1]
Output: 1
Explanation: With k = 1, exchanging 3 and 1 is allowed because 3 AND 1 = 1. This produces [0,1,2,3], and no larger k works.

Example 2

Input: nums = [0,1,3,2]
Output: 2
Explanation: With k = 2, exchanging 3 and 2 produces [0,1,2,3], since 3 AND 2 = 2. This is the largest valid k.

Example 3

Input: nums = [3,2,1,0]
Output: 0
Explanation: The permutation can be sorted when k = 0, but every positive k prevents the necessary exchanges.

3. Constraints

• 1 <= n == nums.length <= 10$^5$
• 0 <= nums[i] <= n - 1
• nums contains every integer from 0 through n - 1 exactly once.

4. Solutions

Bit Manipulation

n = nums.size()
Time complexity: O(n)
Space complexity: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
public:
    int sortPermutation(const vector<int> &nums) {
        int k = -1;
        for (int i = 0, n = nums.size(); i < n; ++i) {
            if (nums[i] != i) {
                k &= nums[i];
            }
        }

        return max(k, 0);
    }
};