LeetCode 3630 - Partition Array for Maximum XOR and AND

The problem asks us to partition an integer array nums into three subsequences A, B, and C such that every element belongs to exactly one subsequence.

leetcodehardarraymathgreedybit-manipulationenumeration

LeetCode Problem 3630

Difficulty: 🔴 Hard
Topics: Array, Math, Greedy, Bit Manipulation, Enumeration

Solution

Problem Understanding

The problem asks us to partition an integer array nums into three subsequences A, B, and C such that every element belongs to exactly one subsequence. The goal is to maximize the sum XOR(A) + AND(B) + XOR(C), where XOR and AND represent the bitwise XOR and AND of the elements in the subsequences. If a subsequence is empty, its contribution is defined as 0.

The input nums is an array of integers with length between 1 and 19, and each integer is between 1 and 10^9. The constraints are tight enough that we cannot rely on simple brute-force enumeration of all partitions for larger arrays without some clever optimization, but small enough that bit manipulation or memoization strategies are feasible. Edge cases include arrays of length 1, arrays with repeated elements, and arrays where one or more subsequences should be empty in the optimal solution.

In essence, the problem combines partitioning, bitwise operations, and combinatorial optimization. Correct solutions must handle all three subsequences and consider the impact of bitwise XOR and AND when combining elements.

Approaches

The brute-force approach considers generating all possible ways to assign each element to one of the three subsequences. For n elements, there are 3^n possible partitions. For each partition, we compute XOR(A) + AND(B) + XOR(C) and track the maximum. This approach is correct because it exhaustively evaluates every partition, but it becomes infeasible for n near 19 because 3^19 is approximately 1.16 billion combinations.

The optimal approach relies on memoization with bitmasking. We can represent subsets with a bitmask and recursively try adding the current element to A, B, or C, caching results for each combination of index and current XOR/AND state. Since XOR can be combined incrementally and AND can also be computed progressively, memoization drastically reduces the number of redundant computations, making the problem feasible even for the maximum constraints.

Approach Time Complexity Space Complexity Notes
Brute Force O(3^n * n) O(n) Enumerates all partitions; too slow for n ≈ 19
Optimal O(n * 2^n * 2^k) O(n * 2^n * 2^k) Uses DP/memoization and bitmasking; feasible due to small n

Here, k represents the number of distinct bits in elements, which is bounded by 30 since nums[i] <= 10^9.

Algorithm Walkthrough

  1. Define a recursive function dfs(index, xorA, andB, xorC) where index is the current position in nums, and xorA, andB, and xorC are the current XOR and AND values for the subsequences.
  2. If index equals the length of nums, return the sum xorA + andB + xorC as the result for this partition path.
  3. For the current element nums[index], recursively call dfs three times: once adding the element to A (update xorA), once adding it to B (update andB), and once adding it to C (update xorC).
  4. Track the maximum of the three recursive results and return it.
  5. Use memoization to store results for each combination of index and XOR/AND states to avoid redundant computations.
  6. Start the recursion with dfs(0, 0, 0, 0) and return the result.

Why it works: The algorithm systematically explores all partitions while caching overlapping subproblems. Since XOR and AND can be computed incrementally, the memoized DFS ensures all valid partitions are considered efficiently without recomputation.

Python Solution

from typing import List
from functools import lru_cache

class Solution:
    def maximizeXorAndXor(self, nums: List[int]) -> int:
        n = len(nums)

        @lru_cache(maxsize=None)
        def dfs(index: int, xorA: int, andB: int, xorC: int) -> int:
            if index == n:
                return xorA + andB + xorC
            num = nums[index]
            # Add num to A
            optionA = dfs(index + 1, xorA ^ num, andB, xorC)
            # Add num to B
            newAndB = num if andB == 0 else andB & num
            optionB = dfs(index + 1, xorA, newAndB, xorC)
            # Add num to C
            optionC = dfs(index + 1, xorA, andB, xorC ^ num)
            return max(optionA, optionB, optionC)

        return dfs(0, 0, 0, 0)

The implementation defines a memoized recursive function using lru_cache. For each element, it considers three placement options and updates XOR or AND values accordingly. The andB handling ensures that if B is empty, the first number initializes it; otherwise, it uses bitwise AND. Memoization prevents recomputation of overlapping states.

Go Solution

package main

func maximizeXorAndXor(nums []int) int64 {
    n := len(nums)
    memo := make(map[[4]int]int64)

    var dfs func(index int, xorA int, andB int, xorC int) int64
    dfs = func(index int, xorA int, andB int, xorC int) int64 {
        if index == n {
            return int64(xorA + andB + xorC)
        }
        key := [4]int{index, xorA, andB, xorC}
        if val, ok := memo[key]; ok {
            return val
        }
        num := nums[index]
        // Add num to A
        optionA := dfs(index+1, xorA^num, andB, xorC)
        // Add num to B
        newAndB := num
        if andB != 0 {
            newAndB = andB & num
        }
        optionB := dfs(index+1, xorA, newAndB, xorC)
        // Add num to C
        optionC := dfs(index+1, xorA, andB, xorC^num)
        res := max(optionA, max(optionB, optionC))
        memo[key] = res
        return res
    }

    return dfs(0, 0, 0, 0)
}

func max(a, b int64) int64 {
    if a > b {
        return a
    }
    return b
}

In Go, we use a map to memoize the recursive calls because Go does not have a built-in lru_cache. The AND initialization and XOR handling follow the same logic as Python. We use int64 for results to prevent overflow from large sums.

Worked Examples

Example 1: nums = [2,3]

Step through DFS:

Index xorA andB xorC Decision Result
0 0 0 0 add 2 to B andB=2
1 0 2 0 add 3 to A xorA=3

Optimal partition: A=[3], B=[2], C=[] → result 5.

Example 2: nums = [1,3,2]

Optimal partition: A=[1], B=[2], C=[3] → result 1 + 2 + 3 = 6.

Example 3: nums = [2,3,6,7]

Optimal partition: A=[7], B=[2,3], C=[6] → result 7 + 2 + 6 = 15.

Complexity Analysis

Measure Complexity Explanation
Time O(3^n) Each element has 3 choices, memoization reduces redundant recomputation, but worst-case still exponential in n
Space O(n * 3^n) Stack depth is O(n), memoization table stores up to O(3^n) states

The recursive branching gives 3 options per element, which leads to an exponential number of potential states. Memoization ensures that overlapping states are computed only once, which makes the solution feasible for n <= 19.

Test Cases

# Provided examples
assert Solution().maximizeXorAndXor([2,3]) == 5  # small array, one empty subsequence
assert Solution().maximizeXorAndXor([1,3,2]) == 6  # optimal split into 3 subsequences
assert Solution().maximizeXorAndXor([2,3,6,7]) == 15  # larger array

# Boundary cases
assert Solution().maximizeXorAndXor([1]) == 1  # single element
assert Solution().maximizeXorAndXor([1,1,1]) == 3  # repeated elements
assert Solution().maximizeXorAndXor([1,2,4,8,16,32,64,128,256,512,1024])

You are given an array nums, no overflow when combining XOR and AND contributions.