What is the brute force approach and complexity for Maximum Subset XOR?

Try all 2^N subsets (each element in or out), XOR each one, keep the largest with time complexity O(N · 2^N) and space complexity O(1).

What is the optimal approach and complexity for Maximum Subset XOR?

Keep one number per highest bit; insert by XOR-ing away high bits; build the answer from the top bit down with optimal time complexity O(20 · N) and space complexity O(20).

How do you identify the pattern for Maximum Subset XOR?

Look for key signals in the prompt: "any group of the array" indicates The answer is a combination of numbers, not just one of them, so the trick is to track combinations by their bits.; "the largest XOR" indicates Maximising XOR is decided bit by bit, from the top bit down.; "values up to 10^6" indicates Every value fits in 20 bits, so the basis has at most 20 slots..

Maximum Subset XOR

Hard·GeeksforGeeks Pro OnlySlight Variation

GeeksforGeeks

Problem Statement

You get an array arr of positive integers. Pick any group of its elements. The group can be one element, all of them, or anything in between. XOR the chosen elements together.

Return the largest value that any such group can give. Every element is at least 1, so one element on its own already gives the largest element. The answer can be bigger than that.

Input

An array arr of length n.

Output

One integer: the largest XOR of any group of elements from arr. The function is int maxSubsetXOR(vector<int> &arr).

Example 1

Input: arr = [2, 4, 5]

Output: 7

2 XOR 5 = 010 XOR 101 = 111 = 7, the largest value. (2 XOR 4 XOR 5 = 3, and 4 XOR 5 = 1.)

Example 2

Input: arr = [9, 8, 5]

Output: 13

8 XOR 5 = 1000 XOR 0101 = 1101 = 13. The pair 9 XOR 5 = 12 is smaller.

Constraints

• 1 ≤ n ≤ 10^5
• 1 ≤ arr[i] ≤ 10^6

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“any group of the array”

→ The answer is a combination of numbers, not just one of them, so the trick is to track combinations by their bits.

“the largest XOR”

→ Maximising XOR is decided bit by bit, from the top bit down.

“values up to 10^6”

→ Every value fits in 20 bits, so the basis has at most 20 slots.

Approach Complexity Ladder

Brute Force — try every subsetO(N · 2^N)O(1)

Try all 2^N subsets (each element in or out), XOR each one, keep the largest

Better — the set of XOR values any subset can makeO(N · 2^20)O(2^20)

Keep every XOR value reachable so far; each new number adds v ^ x for each value v

Optimal — XOR linear basis (one stored number per top bit)O(20 · N)O(20)

Keep one number per highest bit; insert by XOR-ing away high bits; build the answer from the top bit down

Brute Force Intuition

Each subset is a bitmask: bit i set means arr[i] is in the group. Loop over all 2^N masks, XOR the chosen elements of each one, and keep the largest result. This tries every choice, so it is correct, but the work doubles with every new element.

Recognition rule for this sub-pattern:

Represent a set of chosen items as bits of an integer, then iterate or DP over masks.

Remember this · Bit Manipulation

Trigger

"Every element appears twice except…", power of two, counting set bits, subsets as bitmasks, O(1) space tricks.

Think

What happens to this problem if I look at each bit separately?

Key question

Which bit operation (XOR, AND, OR, shift) cancels or isolates what I need?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Bit Manipulation translate into production architectures and low-level memory mechanics.

LLD Architecture