Partition array to minimize xor

Array Dynamic Programming Bit Manipulation Prefix Sum

41.1% acceptance

Feb 25, 2026

107

You are given an integer array nums and an integer k. Partition nums into k non-empty subarrays. For each subarray, compute XOR of all elements. Return the minimum possible value of the maximum XOR among these k subarrays.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn min_xor(nums: Vec<i32>, k: i32) -> i32 {
    let n = nums.len();
    let k = k as usize;

    // Prefix XOR
    let mut prefix = vec![0i32; n + 1];
    for i in 0..n {
      prefix[i + 1] = prefix[i] ^ nums[i];
    }

    // XOR of subarray [i..j] = prefix[j+1] ^ prefix[i]
    // We need to cut n elements into k parts.
    // DP: dp[i][j] = min max XOR for first j elements partitioned into i parts.
    // dp[1][j] = prefix[j] (XOR of nums[0..j-1])
    // dp[i][j] = min over l < j: max(dp[i-1][l], prefix[j] ^ prefix[l])

    let inf = i32::MAX;
    let mut dp = vec![vec![inf; n + 1]; k + 1];
    dp[0][0] = 0;
    for i in 1..=k {
      for j in i..=(n - k + i) {
        for l in (i - 1)..j {
          if dp[i - 1][l] == inf { continue; }
          let seg_xor = prefix[j] ^ prefix[l];
          let val = dp[i - 1][l].max(seg_xor);
          if val < dp[i][j] {
            dp[i][j] = val;
          }
        }
      }
    }

    dp[k][n]
  }
}