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.
Examples
Example 1
Input: nums = [1,2,3], k = 2
Output: 1
Explanation:
The optimal partition is [1] and [2, 3] .
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] .
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] .
The maximum XOR among the subarrays is 0, which is the minimum possible.
Constraints
1 <= nums.length <= 250
1 <= nums[i] <= 109
1 <= k <= n
3599. Partition Array to Minimize XOR
Medium
30 Points
Array
Dynamic Programming
Bit Manipulation
Prefix Sum
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.
Examples
Example 1
Input: nums = [1,2,3], k = 2
Output: 1
Explanation:
The optimal partition is [1] and [2, 3] .
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] .
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] .
The maximum XOR among the subarrays is 0, which is the minimum possible.
Constraints
1 <= nums.length <= 250
1 <= nums[i] <= 109
1 <= k <= n
Partition Array to Minimize XOR - Practice Coding | SlaveCode