Skip to main content
Talentd

Partition Array for Maximum XOR and AND - Solution & Explanation

HardArrayMathGreedyBit Manipulation4 min readAsked at: Google
Practice this problem

Problem Statement

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) = 3
  • B = [2], AND(B) = 2
  • C = [], 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) = 1
  • B = [2], AND(B) = 2
  • C = [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) = 7
  • B = [2,3], AND(B) = 2
  • C = [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 <= 19
  • 1 <= nums[i] <= 109

Approach Overview

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

Solutions for this problem are being prepared.

Try solving it yourself

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force EnumerationO(n^2)O(1)Useful for validating logic or when constraints are very small
Prefix XOR + Suffix ANDO(n)O(n)General case; fastest practical solution for large arrays
Bitwise Greedy OptimizationO(n * B)O(1)When memory is constrained or when reasoning directly per bit

Video Solution

Leetcode 3630. Partition Array for Maximum XOR and AND | Part - 1 • ExpertFunda • 342 views views

Watch 1 more video solutions →

Frequently Asked Questions

Is Partition Array for Maximum XOR and AND easy or hard?
The problem is considered Hard because it combines partition enumeration with non‑trivial bit manipulation reasoning. While the brute force idea is simple, identifying the prefix/suffix optimization and understanding how XOR and AND behave across partitions requires deeper algorithmic insight.
Partition Array for Maximum XOR and AND Python/Java solution
Most implementations maintain a running prefix XOR while computing a suffix AND array from the right. The logic is identical across Python, Java, C++, and Go: preprocess values, iterate over partition points, and track the maximum bitwise score.
How to solve Partition Array for Maximum XOR and AND in O(n)?
Precompute two arrays: prefix XOR and suffix AND. The prefix array stores XOR from the start to index i, and the suffix array stores AND from index i to the end. Iterate through all split points and combine the precomputed values to evaluate the score instantly, resulting in a linear scan.
What is the best approach for Partition Array for Maximum XOR and AND?
The most practical solution uses prefix XOR and suffix AND preprocessing. Compute the XOR of elements up to each index and the AND of elements from each index to the end. Then evaluate every partition in O(1) time. The overall complexity becomes O(n) time with O(n) extra space.
Is Partition Array for Maximum XOR and AND asked at Google/Amazon/Meta?
Bit manipulation and partition optimization problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants involving XOR maximization, prefix computations, and greedy bit reasoning are especially common in senior-level algorithm rounds.
What data structure is used in Partition Array for Maximum XOR and AND?
The solution mainly relies on arrays for prefix and suffix preprocessing. The algorithm also uses bit manipulation operations such as XOR and AND to compute values efficiently across partitions.
What is the time complexity of Partition Array for Maximum XOR and AND?
The brute force approach runs in O(n^2) because each partition recomputes XOR and AND values. With prefix XOR and suffix AND preprocessing, the complexity improves to O(n) time and O(n) space. Bitwise greedy variations typically run in O(n * B) where B is the number of bits (usually 32).

Ready to solve this problem?

Practice Partition Array for Maximum XOR and AND with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays