1class 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}
40

1class 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};
36

1/**
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}
36