Largest Fixed AND Value for Sorting a Permutation
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
You are given `nums`, a permutation of the integers from `0` through `n - 1`.
Choose one nonnegative integer `k`. During the entire sorting process, you may swap two current elements only when their bitwise AND equals `k`:
```text
nums[i] AND nums[j] == k
```
Return the greatest `k` for which some sequence of permitted swaps sorts the permutation into non-decreasing order. If the input is already sorted, return `0` as specified by the problem.
```cpp
class Solution {
public:
int sortPermutation(vector<int>& nums);
};
```
### Examples
**Example 1:**
```text
Input: nums = [0,1,2,3,4,5,7,6]
Output: 6
Explanation: With k = 6, swapping the last two elements sorts the permutation because 7 AND 6 equals 6. No larger k permits the required change involving value 6.
```
**Example 2:**
```text
Input: nums = [0,1,2,5,4,7,6,3]
Output: 1
Explanation: A permitted sequence exists for k = 1 and sorts the permutation. No greater value of k allows all required changes. The result is k, not the number of swaps.
```
### Constraints
- `1 <= n == nums.length <= 100000`.
- `0 <= nums[i] <= n - 1`.
- Every integer from `0` through `n - 1` appears exactly once.
### Clarifying Questions
- Can `k` change between swaps? No; choose one value for the entire sequence.
- Are the swap conditions checked using the values currently at the two indices? Yes.
- Must elements already in their final positions remain there throughout the sequence? No. The final permutation must be sorted.
- Must a swap sequence be returned? No, return only the maximum feasible `k`.
- What is returned for an already sorted permutation, including `[0]`? `0`.
### What a Strong Answer Covers
- The exact bitwise condition and one fixed `k` for all swaps.
- Both an upper bound on a feasible `k` and a reason that the returned bound can be attained.
- The already-sorted convention and the full permutation guarantee.
- Correct handling of values that begin in their final positions, with resource bounds for the largest input.
### Follow-up Questions
- What additional output and space requirements would arise if a valid swap sequence were also requested?
- What return convention would need to be reconsidered if the already-sorted special case were removed?
```hint Use the misplaced values, then prove feasibility
Every value outside its target position must participate in a swap. Consider which bits a feasible k could share with all such values. The fact that every value from 0 through n - 1 is present also matters when proving that the bound can be achieved.
```
Overview: Find the largest fixed bitwise-AND value that permits sorting a permutation by allowed swaps. Includes examples, a feasibility proof, and a full C++ solution.
