You are given an integer array nums and an integer k.
Your task is to partition nums into k non-empty subarrays. For each subarray, compute the bitwise XOR of all its elements.
Return the minimum possible value of the maximum XOR among these k subarrays.
Example 1:
Input: nums = [1,2,3], k = 2
Output: 1
Explanation:
The optimal partition is [1] and [2, 3].
1.2 XOR 3 = 1.The maximum XOR among the subarrays is 1, which is the minimum possible.
Example 2:
Input: nums = [2,3,3,2], k = 3
Output: 2
Explanation:
The optimal partition is [2], [3, 3], and [2].
2.3 XOR 3 = 0.2.The maximum XOR among the subarrays is 2, which is the minimum possible.
Example 3:
Input: nums = [1,1,2,3,1], k = 2
Output: 0
Explanation:
The optimal partition is [1, 1] and [2, 3, 1].
1 XOR 1 = 0.2 XOR 3 XOR 1 = 0.The maximum XOR among the subarrays is 0, which is the minimum possible.
Constraints:
1 <= nums.length <= 2501 <= nums[i] <= 1091 <= k <= nProblem Overview: You are given an array and must split it into multiple contiguous partitions so the total XOR value across the partitions is minimized. The challenge is deciding where to cut the array while efficiently computing XOR values for each segment.
Approach 1: Brute Force Partition Enumeration (Exponential Time)
Generate every possible way to partition the array and compute the XOR of each segment. For each partition configuration, iterate through the segments, calculate their XOR, and track the minimum total value. This approach directly models the problem but quickly becomes infeasible because the number of partitions grows exponentially with the array size. Time complexity is O(2^n * n) and space complexity is O(n) due to recursion or stack usage.
Approach 2: Dynamic Programming with Prefix XOR (O(n^2))
Use dynamic programming to build the optimal answer incrementally. Let dp[i] represent the minimum XOR cost to partition the prefix ending at index i. Precompute prefix XOR values so the XOR of any subarray [l, r] can be calculated in O(1). For each position i, iterate over all possible previous cut points j and update dp[i] = min(dp[i], dp[j] + xor(j+1..i)). This reduces repeated XOR computation using prefix XOR and relies on efficient state transitions. Time complexity is O(n^2) and space complexity is O(n).
Approach 3: Bit-Aware DP Optimization (O(n^2) with Reduced Constant)
Because XOR operates at the bit level, some implementations track transitions while considering how bits cancel when extending a segment. Instead of recomputing values repeatedly, you maintain running XOR values as the right boundary expands. This keeps the same DP structure but minimizes repeated bit operations. The approach still uses bit manipulation and prefix XOR to compute segment costs efficiently. Time complexity remains O(n^2) with O(n) space, but performs better in practice for large arrays.
Recommended for interviews: The dynamic programming approach with prefix XOR is the expected solution. It shows you understand how to model partition problems using DP states and how prefix XOR enables constant-time subarray XOR queries. Brute force demonstrates the baseline idea, but the optimized DP approach shows the algorithmic thinking interviewers look for.
We define f[i][j] as the minimum possible value of the maximum XOR among all ways to partition the first i elements into j subarrays. Initially, set f[0][0] = 0, and all other f[i][j] = +infty.
To quickly compute the XOR of a subarray, we can use a prefix XOR array g, where g[i] represents the XOR of the first i elements. For the subarray [h + 1...i] (with indices starting from 1), its XOR value is g[i] \oplus g[h].
Next, we iterate i from 1 to n, j from 1 to min(i, k), and h from j - 1 to i - 1, where h represents the end position of the previous subarray (indices starting from 1). We update f[i][j] using the following state transition equation:
$
f[i][j] = min_{h \in [j - 1, i - 1]} max(f[h][j - 1], g[i] \oplus g[h])
Finally, we return f[n][k], which is the minimum possible value of the maximum XOR when partitioning the entire array into k subarrays.
The time complexity is O(n^2 times k), and the space complexity is O(n times k), where n$ is the length of the array.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Partition Enumeration | O(2^n * n) | O(n) | Small arrays or when exploring the baseline idea |
| Dynamic Programming with Prefix XOR | O(n^2) | O(n) | General optimal approach for most constraints |
| Bit-Aware DP Optimization | O(n^2) | O(n) | When minimizing repeated XOR computation in large inputs |
Leetcode 3599 | Partition array to minimize xor | Leetcode weekly contest 456 | Dynamic programming • CodeWithMeGuys • 1,244 views views
Watch 7 more video solutions →Practice Partition Array to Minimize XOR with our built-in code editor and test cases.
Practice on FleetCode