Maximum k to sort a permutation

Array Bit Manipulation

37.2% acceptance

Feb 25, 2026

You are given an integer array nums of length n, where nums is a permutation of the numbers in the range [0..n - 1]. You may swap elements at indices i and j only if nums[i] AND nums[j] == k, where AND denotes the bitwise AND operation and k is a non-negative integer. Return the maximum value of k such that the array can be sorted in non-decreasing order using any number of such swaps. If nums is already sorted, return 0.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn sort_permutation(nums: Vec<i32>) -> i32 {
    let _n = nums.len();
    // Check if already sorted
    if nums.iter().enumerate().all(|(i, &v)| v as usize == i) {
      return 0;
    }
    // For a given k, we can swap any two elements a, b where a & b == k.
    // This means both a and b have all bits of k set (a & b == k implies a superset of k bits,
    // and their AND is exactly k, so they share exactly k bits).
    // 
    // For k = 0: we can swap any two elements that AND to 0 (e.g. complementary pairs).
    //   Actually nums[i] AND nums[j] == 0 means they have no common bits.
    //   This gives very limited connectivity.
    //
    // Key insight: for a given k, elements that can be mutually interchanged are those
    // where a & b == k for all pairs. This means all elements in the swap group
    // must have exactly the bits of k in common (and additional different bits).
    // 
    // The maximum k is determined by: try k from large to small.
    // For a given k, elements that CAN be swapped are those with (a & b == k).
    // Two elements a, b can be swapped if a & b == k.
    // This forms a graph; connected components of this graph determine what can be rearranged.
    // 
    // For k to work: each connected component (via swap-graph) must contain exactly the right values.
    //
    // Observation: if a & b == k, then a | k == a and b | k == b (k is subset of both).
    // Also a != b (permutation, distinct), and a & b gives exactly k.
    //
    // Simpler: for k, all values that have all bits of k set can potentially be in swap chains.
    // Values that DON'T have all bits of k set cannot participate in any swap,
    // so they must already be in the correct position.
    //
    // For maximum k: try all possible k values (0 to max_val).
    // But n can be 10^5, so k up to 10^5.
    // 
    // Better approach: 
    // Elements that are NOT in correct position form "misplaced" pairs.
    // The answer is the AND of all misplaced elements... no.
    //
    // Actually the answer is the bitwise AND of all elements that are out of place.
    // Because:
    // - For any two swappable elements a,b: a&b == k.
    // - If k is the answer, every misplaced element must participate in some swap.
    // - So every misplaced element a satisfies a & (at least one other) = k.
    // - This means k must be a submask of every misplaced element.
    // - The maximum such k is AND of all misplaced elements.
    // - We need to verify this actually allows sorting (i.e., within the component
    //   of elements with bits k set, all misplaced ones can be sorted).
    //
    // Let's verify with examples:
    // [0,3,2,1]: misplaced = {3,1} (nums[1]=3 should be 1, nums[3]=1 should be 3).
    //   Also nums[2]=2 is correct.
    //   AND of misplaced = 3&1 = 1. k=1. Can we swap 3 and 1? 3&1=1=k. Yes. -> sorted.
    // [3,2,1,0]: misplaced = {3,2,1,0}. AND = 3&2&1&0 = 0. k=0.
    
    let mut and_misplaced = !0i32;
    let mut any_misplaced = false;
    for (i, &v) in nums.iter().enumerate() {
      if v as usize != i {
        and_misplaced &= v;
        any_misplaced = true;
      }
    }
    if !any_misplaced { return 0; }
    and_misplaced
  }
}