Problem Description

You have an integer array nums (0-indexed). You can perform a special operation on this array:

1. Pick two different indices i and j from the array
2. Find a bit position k where both nums[i] and nums[j] have a 1 in their binary representation at that position (0-indexed from right)
3. Subtract 2^k from both nums[i] and nums[j]

A subarray is called beautiful if you can make all its elements equal to 0 by applying this operation any number of times (including zero times).

Your task is to count how many beautiful subarrays exist in the given array.

Key observations:

• The operation essentially "turns off" a specific bit that's 1 in both selected numbers
• For a subarray to be reducible to all zeros, every bit position across all numbers must have an even count of 1s (so they can be paired off and eliminated)
• If a bit appears an odd number of times, it cannot be eliminated since the operation requires pairing

Example understanding: If you have [5, 3, 2] which is [101, 011, 010] in binary:

• Bit 0: appears in positions 0 and 1 (even count ✓)
• Bit 1: appears in positions 1 and 2 (even count ✓)
• Bit 2: appears in position 0 only (odd count ✗)

This subarray wouldn't be beautiful because bit 2 appears an odd number of times.

The solution uses XOR properties: if two prefix XOR values are the same, the subarray between them has all bits appearing an even number of times (since XOR of identical values is 0, meaning all bits canceled out evenly).

Intuition

Let's think about what makes a subarray "beautiful". We need to pair up 1s at each bit position to eliminate them. This means each bit position must have an even count of 1s across all numbers in the subarray.

Here's the key insight: XOR operation perfectly captures this "even/odd" property! When we XOR numbers:

• XORing two 1s gives 0 (even count → eliminated)
• XORing a single 1 gives 1 (odd count → remains)

So if we XOR all numbers in a subarray and get 0, it means every bit position has an even count - exactly what we need for a beautiful subarray!

Now, how do we efficiently check all subarrays? Instead of checking each subarray individually (which would be O(n²)), we can use prefix XOR. If we maintain a running XOR from the start:

• prefix[i] = XOR of all elements from index 0 to i
• For any subarray from index i+1 to j: its XOR equals prefix[j] ^ prefix[i]

The magic happens when prefix[j] ^ prefix[i] = 0, which means prefix[j] = prefix[i]. So we're looking for positions where the prefix XOR repeats!

This transforms our problem into: "Count pairs of indices with the same prefix XOR value."

We use a hash table to track how many times each prefix XOR value has appeared. For each new position:

1. Calculate the current prefix XOR
2. Count how many times we've seen this value before (these form beautiful subarrays ending at current position)
3. Add this prefix XOR to our hash table for future positions

Starting with {0: 1} handles the edge case where the entire prefix from the start forms a beautiful subarray (when current prefix XOR is 0).

Learn more about Prefix Sum patterns.

Solution Approach

We implement the solution using prefix XOR combined with a hash table to efficiently count beautiful subarrays.

Algorithm Steps:

1. Initialize the hash table: Start with cnt = {0: 1}. This means we've seen the XOR value 0 once before we start (representing an empty prefix). This handles cases where a prefix from the start forms a beautiful subarray.

2. Initialize variables:

   • ans = 0 to store our count of beautiful subarrays
   • mask = 0 to maintain the running XOR (prefix XOR)

3. Traverse the array: For each element x in nums:

   • Update prefix XOR: mask ^= x - this gives us the XOR of all elements from index 0 to current position
   • Count beautiful subarrays: ans += cnt[mask] - if we've seen this mask value k times before, it means there are k subarrays ending at the current position that are beautiful
   • Update hash table: cnt[mask] += 1 - record that we've seen this prefix XOR value one more time

4. Return the result: ans contains the total count of beautiful subarrays

Why this works:

• When mask at position j equals mask at position i (where i < j), the subarray from i+1 to j has XOR = 0
• XOR = 0 means all bits appear an even number of times in that subarray
• Even bit counts mean we can pair and eliminate all bits using the given operation
• Therefore, the subarray is beautiful

Time Complexity: O(n) where n is the length of the array - we traverse once Space Complexity: O(n) for the hash table in worst case (all different prefix XOR values)

The elegance of this solution lies in recognizing that the "pairing" nature of the operation translates perfectly to the XOR operation, allowing us to reduce a seemingly complex problem to finding matching prefix XOR values.

Example Walkthrough

Let's walk through the algorithm with nums = [4, 3, 1, 2, 4].

First, let's understand what we're looking for. In binary:

• 4 = 100
• 3 = 011
• 1 = 001
• 2 = 010
• 4 = 100

Step-by-step execution:

Initialization:

• cnt = {0: 1} (we've "seen" XOR value 0 once before starting)
• ans = 0 (no beautiful subarrays found yet)
• mask = 0 (running XOR value)

Index 0 (x = 4):

• mask = 0 ^ 4 = 4 (binary: 100)
• Check cnt[4] = 0 (haven't seen mask=4 before)
• ans = 0 + 0 = 0
• Update cnt[4] = 1
• State: cnt = {0: 1, 4: 1}, ans = 0

Index 1 (x = 3):

• mask = 4 ^ 3 = 7 (binary: 111)
• Check cnt[7] = 0 (haven't seen mask=7 before)
• ans = 0 + 0 = 0
• Update cnt[7] = 1
• State: cnt = {0: 1, 4: 1, 7: 1}, ans = 0

Index 2 (x = 1):

• mask = 7 ^ 1 = 6 (binary: 110)
• Check cnt[6] = 0 (haven't seen mask=6 before)
• ans = 0 + 0 = 0
• Update cnt[6] = 1
• State: cnt = {0: 1, 4: 1, 7: 1, 6: 1}, ans = 0

Index 3 (x = 2):

• mask = 6 ^ 2 = 4 (binary: 100)
• Check cnt[4] = 1 (we've seen mask=4 once at index 0!)
• ans = 0 + 1 = 1 ✓ Found beautiful subarray [3, 1, 2]
• Update cnt[4] = 2
• State: cnt = {0: 1, 4: 2, 7: 1, 6: 1}, ans = 1

Index 4 (x = 4):

• mask = 4 ^ 4 = 0 (binary: 000)
• Check cnt[0] = 1 (we've seen mask=0 once - the initial value!)
• ans = 1 + 1 = 2 ✓ Found beautiful subarray [4, 3, 1, 2, 4]
• Update cnt[0] = 2
• Final state: cnt = {0: 2, 4: 2, 7: 1, 6: 1}, ans = 2

Result: 2 beautiful subarrays

Let's verify our found subarrays:

1. [3, 1, 2] (indices 1-3): XOR = 3 ^ 1 ^ 2 = 0 ✓

   • In binary: 011 ^ 001 ^ 010 = 000
   • All bits appear even times, so it's beautiful

2. [4, 3, 1, 2, 4] (indices 0-4): XOR = 4 ^ 3 ^ 1 ^ 2 ^ 4 = 0 ✓

   • In binary: 100 ^ 011 ^ 001 ^ 010 ^ 100 = 000
   • All bits appear even times, so it's beautiful

The algorithm correctly identifies when prefix XOR values repeat, indicating that the subarray between those positions has XOR = 0 and is therefore beautiful.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm iterates through the array nums exactly once. For each element in the array:

• XOR operation with mask takes O(1) time
• Dictionary lookup cnt[mask] takes O(1) average time
• Dictionary update cnt[mask] += 1 takes O(1) average time
• Addition operation for ans takes O(1) time

Since we perform constant-time operations for each of the n elements, the overall time complexity is O(n), where n is the length of the array nums.

Space Complexity: O(n)

The space complexity is determined by the Counter dictionary cnt which stores the frequency of each unique XOR prefix value. In the worst case, all prefix XOR values are distinct, which would require storing n + 1 entries (including the initial {0: 1}). Therefore, the space complexity is O(n), where n is the length of the array nums.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Forgetting to Initialize the Counter with {0: 1}

The Problem: A common mistake is initializing an empty counter without the base case {0: 1}. This causes the algorithm to miss beautiful subarrays that start from index 0.

Why it happens: When a prefix XOR equals 0, it means the entire subarray from the beginning is beautiful. Without {0: 1}, we don't count these cases.

Example: For array [4, 3, 1, 2, 4], the prefix XOR at index 3 is 0 (4^3^1^2 = 0). Without the initial {0: 1}, we'd miss counting the subarray [4, 3, 1, 2].

Solution:

# Wrong
prefix_xor_count = Counter()  # Missing base case

# Correct
prefix_xor_count = Counter({0: 1})  # Handles subarrays from start

Pitfall 2: Updating Counter Before Adding to Result

The Problem: Incrementing prefix_xor_count[current_xor] before adding its value to beautiful_count leads to overcounting.

Why it happens: We want to count how many times we've seen this XOR value before the current position, not including the current position itself.

Example:

# Wrong - counts current position in the result
for num in nums:
    current_xor ^= num
    prefix_xor_count[current_xor] += 1  # Updated first
    beautiful_count += prefix_xor_count[current_xor]  # Now includes current

# Correct - only counts previous occurrences
for num in nums:
    current_xor ^= num
    beautiful_count += prefix_xor_count[current_xor]  # Count previous
    prefix_xor_count[current_xor] += 1  # Then update

Pitfall 3: Misunderstanding XOR Properties

The Problem: Attempting to track individual bit frequencies instead of using XOR, leading to complex and inefficient solutions.

Why it happens: The problem statement talks about bits appearing even/odd times, which might lead to tracking bit counts explicitly.

Wrong approach:

# Overly complex - tracking each bit position
def countBits(subarray):
    bit_counts = [0] * 32
    for num in subarray:
        for bit in range(32):
            if num & (1 << bit):
                bit_counts[bit] += 1
    return all(count % 2 == 0 for count in bit_counts)

Correct approach: Using XOR naturally handles the even/odd property since a ^ a = 0 for any value a.

Pitfall 4: Integer Overflow Concerns (Language-Specific)

The Problem: In languages with fixed integer sizes, XOR operations on large numbers might cause unexpected behavior.

Solution: Python handles arbitrary precision integers automatically, but in other languages:

# For other languages, ensure proper data types
# C++: use long long or unsigned int
# Java: use long if needed

Pitfall 5: Not Understanding Why XOR Works

The Problem: Using the XOR solution without understanding leads to errors when modifying or debugging the code.

Key insight to remember:

• XOR of a number with itself is 0: a ^ a = 0
• XOR is commutative and associative: order doesn't matter
• If subarray has XOR = 0, every bit appears even times
• The operation in the problem (subtracting 2^k from two numbers) is equivalent to flipping the k-th bit in both numbers
• Beautiful subarray ≡ XOR of all elements = 0 ≡ all bits can be paired and eliminated