3599. Partition Array to Minimize XOR
Problem Description
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.
Intuition
To solve the problem, we want to split the array into k parts so that the largest XOR result among these parts is as small as possible. Since XOR is not easily divisible like sum, the challenge is to carefully choose the split points.
Instead of trying every possible way to split, we can use dynamic programming. The key idea is to keep track of the minimum possible "maximum XOR" we can get when dividing the first i elements into j subarrays. We use prefix XOR, which lets us quickly find the XOR of any subarray using g[i] ^ g[h], making it efficient to check possible partitions.
By systematically building up solutions for small parts and combining them, we avoid repeatedly calculating the same possibilities and efficiently find the optimal way to partition the array.
Solution Approach
This problem is solved using dynamic programming and prefix XOR.
First, create a prefix XOR array g where g[i] contains the XOR of the first i numbers (with g[0] = 0). This allows for quick computation of any subarray XOR: the XOR of nums[h] to nums[i-1] is g[i] ^ g[h].
Define a dynamic programming table f[i][j], which represents the minimum possible value of the maximum XOR when partitioning the first i elements into j subarrays. Initialize all entries in f as infinity except f[0][0] = 0 because zero elements partitioned into zero groups has a maximum XOR of 0.
Iterate through all possible i (from 1 to n, the array length), and for each possible number of subarrays j (from 1 to min(i, k)), look at all partition points h (from j-1 to i-1). For each possible previous partition, update f[i][j] as the minimum value of the maximum between the previous subarray's result f[h][j-1] and the current subarray's XOR (g[i] ^ g[h]):
f[i][j] = min(f[i][j], max(f[h][j-1], g[i] ^ g[h]))
After filling in the table, the answer is f[n][k], representing the smallest possible maximum XOR for splitting the array into k subarrays. The prefix XOR speeds up each partition check, and the DP ensures all subproblems are efficiently solved without recomputation.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's take a small example:
nums = [3, 8, 2, 6], k = 2.
Step 1: Build Prefix XOR
- Prefix XOR array
g(withg[0] = 0):g[1] = 0 ^ 3 = 3g[2] = 3 ^ 8 = 11g[3] = 11 ^ 2 = 9g[4] = 9 ^ 6 = 15So,g = [0, 3, 11, 9, 15].
Step 2: Initialize DP Table
Let f[i][j] be the minimum possible value of the maximum XOR when partitioning the first i elements into j subarrays.
Initialize f with infinity, except f[0][0] = 0.
Step 3: Fill DP Table
We want to compute f[4][2] (n = 4, k = 2).
Case 1: Partition between 1 and 3
Check all possible split points (h from j-1 = 1 to i-1 = 3):
-
Partition at
h = 1: First subarray:[3], XOR =g[1] ^ g[0] = 3 ^ 0 = 3Second subarray:[8,2,6], XOR =g[4] ^ g[1] = 15 ^ 3 = 12So, max XOR =max(3, 12) = 12 -
Partition at
h = 2: First subarray:[3,8], XOR =g[2] ^ g[0] = 11 ^ 0 = 11Second subarray:[2,6], XOR =g[4] ^ g[2] = 15 ^ 11 = 4So, max XOR =max(11, 4) = 11 -
Partition at
h = 3: First subarray:[3,8,2], XOR =g[3] ^ g[0] = 9 ^ 0 = 9Second subarray:[6], XOR =g[4] ^ g[3] = 15 ^ 9 = 6So, max XOR =max(9, 6) = 9
Now take the minimum among 12, 11, 9.
So, f[4][2] = 9.
Step 4: Result
The minimum possible value of the maximum XOR among the two subarrays is 9.
Key Steps Illustrated:
- Build prefix XOR for fast subarray XOR computation.
- Use dynamic programming to test all split points for each subarray count.
- For each split, choose the minimal possible worst-case maximum XOR.
Solution Implementation
1from typing import List
2from math import inf
3
4class Solution:
5 def minXor(self, nums: List[int], k: int) -> int:
6 n = len(nums)
7
8 # Prefix XORs: prefixXor[i] = nums[0] ^ nums[1] ^ ... ^ nums[i-1]
9 prefix_xor = [0] * (n + 1)
10 for i in range(1, n + 1):
11 prefix_xor[i] = prefix_xor[i - 1] ^ nums[i - 1]
12
13 # DP table: dp[i][j] = min largest XOR among j groups from first i elements
14 dp = [[inf] * (k + 1) for _ in range(n + 1)]
15 dp[0][0] = 0 # No elements, zero groups, max XOR = 0
16
17 # Fill the DP table
18 for i in range(1, n + 1): # Last considered index
19 for j in range(1, min(i, k) + 1): # Number of groups
20 for h in range(j - 1, i): # Previous partitioning index
21 # The XOR of subarray (h, i-1) is prefix_xor[i] ^ prefix_xor[h]
22 curr_xor = prefix_xor[i] ^ prefix_xor[h]
23 # The max in this partition: max of previous and current group
24 dp[i][j] = min(dp[i][j], max(dp[h][j - 1], curr_xor))
25
26 return dp[n][k]
271class Solution {
2 /**
3 * Given an integer array nums and an integer k, partition nums into k contiguous subarrays
4 * such that the largest subarray XOR value is minimized.
5 * Returns that minimum possible value.
6 */
7 public int minXor(int[] nums, int k) {
8 int n = nums.length;
9
10 // prefixXor[i] stores the XOR of nums[0] to nums[i - 1]
11 int[] prefixXor = new int[n + 1];
12 for (int i = 1; i <= n; ++i) {
13 prefixXor[i] = prefixXor[i - 1] ^ nums[i - 1];
14 }
15
16 // dp[i][j]: the minimum possible maximum subarray XOR
17 // for partitioning the first i elements into j parts
18 int[][] dp = new int[n + 1][k + 1];
19 for (int i = 0; i <= n; ++i) {
20 Arrays.fill(dp[i], Integer.MAX_VALUE);
21 }
22 dp[0][0] = 0; // base case: zero elements, zero partitions, value 0
23
24 // Fill DP table
25 for (int i = 1; i <= n; ++i) {
26 // Number of partitions can be at most i (cannot partition into more groups than elements)
27 for (int j = 1; j <= Math.min(i, k); ++j) {
28 // Try all possible previous partition end positions
29 for (int h = j - 1; h < i; ++h) {
30 // partition between h and i, subarray XOR=[h..i - 1] = prefixXor[i] ^ prefixXor[h]
31 int currentXor = prefixXor[i] ^ prefixXor[h];
32 dp[i][j] = Math.min(dp[i][j], Math.max(dp[h][j - 1], currentXor));
33 }
34 }
35 }
36
37 return dp[n][k];
38 }
39}
401class Solution {
2public:
3 // Function to partition the array nums into k subarrays
4 // such that the maximum XOR-sum of any partition is minimized.
5 int minXor(vector<int>& nums, int k) {
6 int n = nums.size();
7
8 // Prefix XOR array: prefixXor[i] = XOR of first i elements (nums[0] to nums[i-1])
9 vector<int> prefixXor(n + 1, 0);
10 for (int i = 1; i <= n; ++i) {
11 prefixXor[i] = prefixXor[i - 1] ^ nums[i - 1];
12 }
13
14 const int INF = numeric_limits<int>::max();
15
16 // DP table: dp[i][j] = minimal possible max-XOR-sum when partitioning
17 // first i elements into j parts.
18 vector<vector<int>> dp(n + 1, vector<int>(k + 1, INF));
19 dp[0][0] = 0; // Base case: 0 elements, 0 partitions, max-XOR-sum is 0
20
21 for (int i = 1; i <= n; ++i) { // First i elements
22 for (int j = 1; j <= min(i, k); ++j) { // Partition count from 1 to k (or i)
23 // Try all possible previous partition points
24 for (int h = j - 1; h < i; ++h) {
25 // dp[h][j-1]: answer for first h elements in j-1 parts
26 // prefixXor[i] ^ prefixXor[h]: XOR of nums[h] to nums[i-1] (i.e., the new part)
27 dp[i][j] = min(dp[i][j], max(dp[h][j - 1], prefixXor[i] ^ prefixXor[h]));
28 }
29 }
30 }
31
32 // Final answer: partition the whole array into k parts
33 return dp[n][k];
34 }
35};
361/**
2 * Finds the minimal largest xor-sum when splitting the array into k contiguous subarrays.
3 * @param nums - Array of numbers to split.
4 * @param k - Number of required subarrays.
5 * @returns The minimal largest xor-sum among all possible k splits.
6 */
7function minXor(nums: number[], k: number): number {
8 const n = nums.length;
9
10 // Prefix XOR array: prefixXor[i] = nums[0] ^ ... ^ nums[i-1]
11 const prefixXor: number[] = Array(n + 1).fill(0);
12 for (let i = 1; i <= n; ++i) {
13 prefixXor[i] = prefixXor[i - 1] ^ nums[i - 1];
14 }
15
16 const INF = Number.MAX_SAFE_INTEGER;
17 // DP array: dp[i][j] = minimal largest xor-sum for first i elements with j cuts (j+1 groups)
18 const dp: number[][] = Array.from({ length: n + 1 }, () => Array(k + 1).fill(INF));
19 dp[0][0] = 0; // Base case: no elements, no groups, max xor is 0
20
21 // i = consider first i elements
22 for (let i = 1; i <= n; ++i) {
23 // j = number of groups we're forming
24 for (let j = 1; j <= Math.min(i, k); ++j) {
25 // Try all possible split positions for previous group
26 for (let h = j - 1; h < i; ++h) {
27 // The xor for the last group (from h to i-1) is prefixXor[i] ^ prefixXor[h]
28 const lastGroupXor = prefixXor[i] ^ prefixXor[h];
29 dp[i][j] = Math.min(dp[i][j], Math.max(dp[h][j - 1], lastGroupXor));
30 }
31 }
32 }
33
34 return dp[n][k];
35}
36Time and Space Complexity
-
Time Complexity: The code uses three nested loops:
- The outermost loop runs
ifrom1ton(O(n)). - The middle loop runs
jfrom1tomin(i, k)(O(k)in the worst case). - The innermost loop runs
hfromj - 1toi - 1(O(n)in the worst case). - Therefore, the total time complexity is
O(n^2 * k).
- The outermost loop runs
-
Space Complexity: The DP table
fis sized(n+1) x (k+1), so the space complexity isO(n * k). The prefix XOR arraygusesO(n)additional space, which is dominated byO(n * k).
What does the following code do?
1def f(arr1, arr2):
2 i, j = 0, 0
3 new_arr = []
4 while i < len(arr1) and j < len(arr2):
5 if arr1[i] < arr2[j]:
6 new_arr.append(arr1[i])
7 i += 1
8 else:
9 new_arr.append(arr2[j])
10 j += 1
11 new_arr.extend(arr1[i:])
12 new_arr.extend(arr2[j:])
13 return new_arr
141public static List<Integer> f(int[] arr1, int[] arr2) {
2 int i = 0, j = 0;
3 List<Integer> newArr = new ArrayList<>();
4
5 while (i < arr1.length && j < arr2.length) {
6 if (arr1[i] < arr2[j]) {
7 newArr.add(arr1[i]);
8 i++;
9 } else {
10 newArr.add(arr2[j]);
11 j++;
12 }
13 }
14
15 while (i < arr1.length) {
16 newArr.add(arr1[i]);
17 i++;
18 }
19
20 while (j < arr2.length) {
21 newArr.add(arr2[j]);
22 j++;
23 }
24
25 return newArr;
26}
271function f(arr1, arr2) {
2 let i = 0, j = 0;
3 let newArr = [];
4
5 while (i < arr1.length && j < arr2.length) {
6 if (arr1[i] < arr2[j]) {
7 newArr.push(arr1[i]);
8 i++;
9 } else {
10 newArr.push(arr2[j]);
11 j++;
12 }
13 }
14
15 while (i < arr1.length) {
16 newArr.push(arr1[i]);
17 i++;
18 }
19
20 while (j < arr2.length) {
21 newArr.push(arr2[j]);
22 j++;
23 }
24
25 return newArr;
26}
27Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By
Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way
Want a Structured Path to Master System Design Too? Don’t Miss This!