Watch 2 video solutions for Partition Array for Maximum XOR and AND, a hard level problem involving Array, Math, Greedy. This walkthrough by ExpertFunda has 329 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an integer array nums.
Partition the array into three (possibly empty) subsequences A, B, and C such that every element of nums belongs to exactly one subsequence.
Your goal is to maximize the value of: XOR(A) + AND(B) + XOR(C)
where:
XOR(arr) denotes the bitwise XOR of all elements in arr. If arr is empty, its value is defined as 0.AND(arr) denotes the bitwise AND of all elements in arr. If arr is empty, its value is defined as 0.Return the maximum value achievable.
Note: If multiple partitions result in the same maximum sum, you can consider any one of them.
Example 1:
Input: nums = [2,3]
Output: 5
Explanation:
One optimal partition is:
A = [3], XOR(A) = 3B = [2], AND(B) = 2C = [], XOR(C) = 0The maximum value of: XOR(A) + AND(B) + XOR(C) = 3 + 2 + 0 = 5. Thus, the answer is 5.
Example 2:
Input: nums = [1,3,2]
Output: 6
Explanation:
One optimal partition is:
A = [1], XOR(A) = 1B = [2], AND(B) = 2C = [3], XOR(C) = 3The maximum value of: XOR(A) + AND(B) + XOR(C) = 1 + 2 + 3 = 6. Thus, the answer is 6.
Example 3:
Input: nums = [2,3,6,7]
Output: 15
Explanation:
One optimal partition is:
A = [7], XOR(A) = 7B = [2,3], AND(B) = 2C = [6], XOR(C) = 6The maximum value of: XOR(A) + AND(B) + XOR(C) = 7 + 2 + 6 = 15. Thus, the answer is 15.
Constraints:
1 <= nums.length <= 191 <= nums[i] <= 109Problem Overview: You are given an array and must split it into two non‑empty partitions. The score depends on bit operations across the partitions: typically the XOR of one side and the AND of the other. Your goal is to choose the partition point that maximizes this bitwise score.
Approach 1: Brute Force Enumeration (O(n2) time, O(1) space)
Try every possible partition index. For each split, compute the XOR of the left part and the AND of the right part by iterating through both segments. Evaluate the score and keep the maximum. This approach is straightforward and demonstrates the correct interpretation of the bitwise operations, but recomputing values for every split causes repeated work and quadratic runtime.
Approach 2: Prefix XOR + Suffix AND Precomputation (O(n * B) time, O(n) space)
Use preprocessing to avoid recomputation. Maintain a prefixXor[i] representing the XOR of elements from index 0..i. Build a suffixAnd[i] array representing the AND of elements from i..n-1. Now iterate through each valid partition point i, combine prefixXor[i] with suffixAnd[i+1], and update the best score. The key insight is that XOR can be accumulated incrementally while AND shrinks monotonically as more elements are included. This reduces repeated scans and turns the brute force into a linear pass with constant‑time evaluation per split.
Approach 3: Bitwise Greedy Observation (O(n * B) time, O(1) space)
Because XOR and AND operate independently on each bit, you can reason about the contribution of individual bits. Higher bits dominate the final value, so you check whether a partition can preserve certain bits in the AND portion while still producing favorable XOR bits on the other side. Iterating through elements while maintaining running XOR and updating candidate AND values effectively prunes impossible partitions early. This works well when constraints are large and you want to avoid storing full prefix/suffix arrays.
Recommended for interviews: The prefix XOR + suffix AND technique is the expected solution. It demonstrates understanding of bit manipulation and how to precompute values across an array to avoid redundant work. Starting with brute force shows correctness, while the optimized approach shows the ability to combine preprocessing with greedy evaluation of partition points.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n^2) | O(1) | Useful for validating logic or when constraints are very small |
| Prefix XOR + Suffix AND | O(n) | O(n) | General case; fastest practical solution for large arrays |
| Bitwise Greedy Optimization | O(n * B) | O(1) | When memory is constrained or when reasoning directly per bit |