#3599

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Partition Array to Minimize XOR

Partition an integer array into k subarrays to minimize the maximum XOR using state transition dynamic programming efficiently.

array dynamic programming bit manipulation prefix sum

Problem Statement

Given an integer array nums and an integer k, partition nums into k non-empty contiguous subarrays. For each subarray, compute the bitwise XOR of its elements.

Return the smallest possible value of the largest XOR among these k subarrays. Constraints: 1 <= nums.length <= 250, 1 <= nums[i] <= 10^9, 1 <= k <= nums.length.

Examples

Example 1

Input: nums = [1,2,3], k = 2

Output: 1

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

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

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

Solution Approach

Use Prefix XORs

Compute prefix XORs to quickly calculate XOR of any subarray. This reduces repeated computation and simplifies state transitions in dynamic programming.

Dynamic Programming State

Define dp[i][j] as the minimum possible maximum XOR for partitioning the first i elements into j subarrays. Update dp[i][j] by considering all valid previous split points.

Iterate Over Partitions Efficiently

For each dp[i][j], loop through potential previous indices to form the last subarray. Use the prefix XOR to compute the new XOR quickly and track the minimal maximum value.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on n * k * n in a naive DP but can be optimized using prefix XOR and careful transitions. Space complexity is O(n*k) to store DP states.

What Interviewers Usually Probe

Focus on dynamic programming with state transitions rather than brute force partitioning.
Expect optimization discussions using prefix XOR to speed up subarray XOR computation.
Clarify handling of subarray splits and maximum XOR updates in DP states.

Common Pitfalls or Variants

Common pitfalls

Forgetting that XOR is not additive and requires prefix XOR for efficient computation.
Incorrectly initializing DP table or mishandling the first subarray state.
Iterating all splits naively without limiting to necessary indices, causing timeouts.

Follow-up variants

Minimize the sum of maximum XORs instead of just the largest XOR.
Partition array into exactly k subarrays with length constraints.
Allow non-contiguous subarrays and minimize the maximum XOR.

FAQ

What is the best way to approach Partition Array to Minimize XOR?

Use state transition dynamic programming with prefix XORs to evaluate subarray partitions efficiently.

How does prefix XOR help in this problem?

Prefix XOR allows O(1) computation of any subarray XOR, which is critical for fast DP state updates.

Can this problem be solved with a greedy approach?

No, greedy approaches fail because XOR is not monotonic; DP ensures all partition combinations are considered.

What is the DP state in Partition Array to Minimize XOR?

dp[i][j] represents the minimal possible maximum XOR for partitioning the first i elements into j subarrays.

What are common mistakes in implementing this DP?

Common mistakes include miscalculating subarray XORs, misinitializing DP, and inefficient iteration over partition points.

terminal

Solution

Solution 1: Dynamic Programming

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$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

min = lambda a, b: a if a < b else b
max = lambda a, b: a if a > b else b


class Solution:
    def minXor(self, nums: List[int], k: int) -> int:
        n = len(nums)
        g = [0] * (n + 1)
        for i, x in enumerate(nums, 1):
            g[i] = g[i - 1] ^ x

        f = [[inf] * (k + 1) for _ in range(n + 1)]
        f[0][0] = 0
        for i in range(1, n + 1):
            for j in range(1, min(i, k) + 1):
                for h in range(j - 1, i):
                    f[i][j] = min(f[i][j], max(f[h][j - 1], g[i] ^ g[h]))
        return f[n][k]

Continue Practicing

#3594 minimum time to transport all individuals #3578 count partitions with max min difference at most k #3575 maximum good subtree score