LeetCode 2588 - Count the Number of Beautiful Subarrays

The problem gives us an array nums, and we are allowed to repeatedly perform a special operation on pairs of elements.

leetcodemediumarrayhash-tablebit-manipulationprefix-sum

LeetCode Problem 2588

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Bit Manipulation, Prefix Sum

Solution

Problem Understanding

The problem gives us an array nums, and we are allowed to repeatedly perform a special operation on pairs of elements.

In one operation, we choose two different indices i and j, and also choose a bit position k such that both nums[i] and nums[j] currently have the kth bit set to 1. We then subtract 2^k from both numbers. Since subtracting 2^k removes exactly that bit from a number, this operation effectively removes one matching set bit from two different elements simultaneously.

A subarray is considered beautiful if, after performing any number of these operations, every element in the subarray can become 0.

The key observation is that operations always remove bits in pairs. For every bit position independently, the total number of set bits across the subarray must therefore be even. If some bit appears an odd number of times, there will always be one leftover bit that cannot be paired away.

This leads directly to an equivalent formulation of the problem:

A subarray is beautiful if and only if the XOR of all elements in the subarray equals 0.

This equivalence is crucial because XOR naturally tracks parity of bits:

  • Even occurrences of a bit cancel out
  • Odd occurrences remain

So instead of simulating operations, we only need to count how many subarrays have XOR equal to 0.

The input size can be as large as 10^5, which immediately rules out expensive cubic or quadratic simulations. We need something close to linear time.

There are also several important edge cases:

  • Arrays containing only zeros, every subarray is beautiful.
  • Arrays with no zero XOR subarrays, the answer is 0.
  • Single-element subarrays are only beautiful if the element itself is 0.
  • Large arrays require an efficient prefix-based solution because enumerating all subarrays directly would be too slow.

Approaches

Brute Force Approach

The most direct solution is to examine every possible subarray.

For each subarray, we compute the XOR of all its elements. If the XOR equals 0, then the subarray is beautiful.

There are O(n^2) subarrays. If we recompute XOR from scratch for every subarray, the total complexity becomes O(n^3).

We can improve slightly by extending subarrays incrementally:

  • Fix a starting index
  • Extend the ending index one step at a time
  • Maintain the running XOR

This reduces the complexity to O(n^2).

The approach is correct because XOR precisely captures whether each bit appears an even number of times. However, with n = 10^5, O(n^2) is far too slow.

Optimal Approach

The key insight comes from prefix XOR.

Define:

prefixXor[i] = nums[0] ^ nums[1] ^ ... ^ nums[i]

The XOR of subarray [l, r] can be computed as:

prefixXor[r] ^ prefixXor[l - 1]

We want this value to equal 0.

That means:

prefixXor[r] = prefixXor[l - 1]

So the problem becomes:

Count how many pairs of equal prefix XOR values exist.

This is identical to the classic "count subarrays with sum/XOR equal to target" pattern.

We use a hash map to track how many times each prefix XOR has appeared so far.

Whenever the current prefix XOR has appeared before, every previous occurrence forms a beautiful subarray ending at the current index.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Enumerates all subarrays and checks XOR
Optimal O(n) O(n) Uses prefix XOR frequencies with a hash map

Algorithm Walkthrough

  1. Initialize a hash map called xor_count.

This map stores how many times each prefix XOR value has appeared so far. 2. Insert the value 0 into the map with frequency 1.

This handles subarrays starting from index 0. Before processing any elements, the prefix XOR is considered 0. 3. Maintain a running variable prefix_xor.

As we iterate through the array, we continuously XOR the current number into this value. 4. For each element in nums:

  • Update the running prefix XOR:
prefix_xor ^= num
  • Check how many times this exact XOR value has appeared before.

Every previous occurrence corresponds to a subarray whose XOR is 0. 5. Add the frequency of prefix_xor from the hash map to the answer.

If prefix_xor has appeared k times before, then there are k beautiful subarrays ending at the current index. 6. Increment the frequency of the current prefix_xor in the hash map.

This makes it available for future subarrays. 7. Continue until all elements are processed. 8. Return the accumulated answer.

Why it works

The algorithm relies on the prefix XOR identity:

XOR(l, r) = prefixXor[r] ^ prefixXor[l - 1]

A subarray has XOR 0 exactly when:

prefixXor[r] = prefixXor[l - 1]

Therefore, every pair of equal prefix XOR values defines one beautiful subarray. The hash map efficiently counts these matching pairs while scanning the array once.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def beautifulSubarrays(self, nums: List[int]) -> int:
        xor_count = defaultdict(int)
        xor_count[0] = 1
        
        prefix_xor = 0
        beautiful_count = 0
        
        for num in nums:
            prefix_xor ^= num
            
            beautiful_count += xor_count[prefix_xor]
            
            xor_count[prefix_xor] += 1
        
        return beautiful_count

The implementation follows the prefix XOR strategy directly.

We first create a frequency map called xor_count. The entry xor_count[0] = 1 is important because it represents the empty prefix before the array begins.

The variable prefix_xor stores the XOR of all elements processed so far.

As we iterate through nums, we update the running XOR using:

prefix_xor ^= num

If this XOR value has appeared before, every previous occurrence corresponds to a beautiful subarray ending at the current position. We therefore add its frequency to the answer.

Finally, we record the current prefix XOR in the map for future iterations.

The entire process runs in linear time because each element is processed exactly once.

Go Solution

func beautifulSubarrays(nums []int) int64 {
    xorCount := make(map[int]int64)
    xorCount[0] = 1

    prefixXor := 0
    var beautifulCount int64 = 0

    for _, num := range nums {
        prefixXor ^= num

        beautifulCount += xorCount[prefixXor]

        xorCount[prefixXor]++
    }

    return beautifulCount
}

The Go implementation mirrors the Python logic closely.

One important difference is that the return type is int64, because the number of subarrays can exceed the range of a standard 32-bit integer. The hash map therefore stores frequencies as int64 values as well.

Go maps return the zero value automatically for missing keys, which makes frequency updates concise.

Worked Examples

Example 1

nums = [4, 3, 1, 2, 4]

We track:

  • prefix_xor
  • Frequency map
  • Number of beautiful subarrays found
Index Num Prefix XOR Previous Frequency New Beautiful Subarrays Total
Start - 0 1 - 0
0 4 4 0 0 0
1 3 7 0 0 0
2 1 6 0 0 0
3 2 4 1 1 1
4 4 0 1 1 2

The beautiful subarrays are:

  1. [3,1,2]
  2. [4,3,1,2,4]

Final answer:

2

Example 2

nums = [1, 10, 4]
Index Num Prefix XOR Previous Frequency New Beautiful Subarrays Total
Start - 0 1 - 0
0 1 1 0 0 0
1 10 11 0 0 0
2 4 15 0 0 0

No prefix XOR repeats, so no subarray has XOR 0.

Final answer:

0

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each element is processed once
Space O(n) Hash map may store up to n distinct prefix XOR values

The algorithm performs a constant amount of work per element. Hash map insertions and lookups are expected O(1) operations, giving overall linear runtime.

The space usage is linear in the worst case because every prefix XOR value could be unique.

Test Cases

from typing import List

class Solution:
    def beautifulSubarrays(self, nums: List[int]) -> int:
        from collections import defaultdict

        xor_count = defaultdict(int)
        xor_count[0] = 1

        prefix_xor = 0
        answer = 0

        for num in nums:
            prefix_xor ^= num
            answer += xor_count[prefix_xor]
            xor_count[prefix_xor] += 1

        return answer

sol = Solution()

assert sol.beautifulSubarrays([4,3,1,2,4]) == 2  # provided example
assert sol.beautifulSubarrays([1,10,4]) == 0  # no beautiful subarrays

assert sol.beautifulSubarrays([0]) == 1  # single zero
assert sol.beautifulSubarrays([5]) == 0  # single non-zero
assert sol.beautifulSubarrays([0,0]) == 3  # every subarray works
assert sol.beautifulSubarrays([1,1]) == 1  # full array XOR is zero
assert sol.beautifulSubarrays([1,2,3]) == 1  # entire array XOR is zero
assert sol.beautifulSubarrays([2,2,2,2]) == 4  # repeated XOR patterns
assert sol.beautifulSubarrays([1,2,1,2]) == 1  # one matching prefix XOR pair
assert sol.beautifulSubarrays([0,0,0]) == 6  # all subarrays beautiful
assert sol.beautifulSubarrays([8,8,8]) == 2  # overlapping beautiful subarrays

Test Summary

Test Why
[4,3,1,2,4] Validates provided example
[1,10,4] Confirms zero-answer case
[0] Smallest beautiful subarray
[5] Single non-zero element
[0,0] Every subarray valid
[1,1] Simple XOR cancellation
[1,2,3] Whole-array XOR equals zero
[2,2,2,2] Multiple repeated prefix XOR values
[1,2,1,2] Tests non-trivial prefix matching
[0,0,0] Large number of valid subarrays
[8,8,8] Overlapping beautiful subarrays

Edge Cases

A very important edge case is when the array contains only zeros. Since XOR with zero does not change anything, every subarray has XOR equal to 0. For an array of length n, the answer becomes n * (n + 1) / 2. The implementation handles this naturally because the prefix XOR remains 0 throughout the traversal, causing repeated matches in the hash map.

Another important case is a single-element array. A subarray containing one non-zero number can never become all zeros because operations require pairs of matching bits across two different indices. The algorithm correctly handles this because a single non-zero value produces a non-zero XOR.

Repeated prefix XOR values are also critical. For example, in [2,2,2,2], the same prefix XOR appears multiple times. Each repeated occurrence creates multiple valid subarrays simultaneously. The frequency map correctly counts all previous occurrences instead of only checking existence, ensuring every valid subarray is counted.

A subtle edge case involves large inputs with many valid subarrays. The total number of beautiful subarrays can exceed 32-bit integer range. The Go implementation explicitly uses int64 for the answer and frequency counts to avoid overflow issues.