#3630

Partition Array for Maximum XOR and AND

hard · 17.6% accepted · 31 likes · top 1%

array · math · greedy · bit manipulation · enumeration

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

Solution