3630. Partition Array for Maximum XOR and AND
SourceWeekly Contest 460 Q4DifficultyHardRating2743
Description
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 inarr. Ifarris empty, its value is defined as 0.AND(arr)denotes the bitwise AND of all elements inarr. Ifarris 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) = 0
The 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) = 3
The 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) = 6
The 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] <= 109
Solutions
Solution 1
Thinking
Partition into \(A,B,C\) and maximize \((\mathrm{XOR}\,A)+(\mathrm{AND}\,B)+(\mathrm{XOR}\,C)\). A linear basis handles which XOR values are constructible.
The XOR of the whole array is fixed. \(\mathrm{AND}\,B\) is the bitwise AND of a subset, so we enumerate candidate AND masks.
For a fixed AND contribution, insert the remaining values into a linear basis. The maximum XOR the basis can form, together with the XOR of the leftovers, yields the \(A,C\) pair. Combining the enumeration with the basis gives the optimum.
1 | |
1 | |
1 | |
1 | |