# Count the Number of Beautiful Subarrays
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-the-number-of-beautiful-subarrays)
Canonical: https://scaleengineer.com/dsa/problems/count-the-number-of-beautiful-subarrays
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array, Hash Table
---
## Problem
You are given a **0-indexed** integer array `nums`. In one operation, you can:

* Choose two different indices `i` and `j` such that `0 <= i, j < nums.length`.
* Choose a non-negative integer `k` such that the `kth` bit (**0-indexed**) in the binary representation of `nums[i]` and `nums[j]` is `1`.
* Subtract `2k` from `nums[i]` and `nums[j]`.

A subarray is **beautiful** if it is possible to make all of its elements equal to `0` after applying the above operation any number of times (including zero).

Return _the number of **beautiful subarrays** in the array_ `nums`.

A subarray is a contiguous **non-empty** sequence of elements within an array.

**Note**: Subarrays where all elements are initially 0 are considered beautiful, as no operation is needed.

**Example 1:**

**Input:** nums = [4,3,1,2,4]
**Output:** 2
**Explanation:** There are 2 beautiful subarrays in nums: [4,3,1,2,4] and [4,3,1,2,4].
- We can make all elements in the subarray [3,1,2] equal to 0 in the following way:
  - Choose [3, 1, 2] and k = 1. Subtract 21 from both numbers. The subarray becomes [1, 1, 0].
  - Choose [1, 1, 0] and k = 0. Subtract 20 from both numbers. The subarray becomes [0, 0, 0].
- We can make all elements in the subarray [4,3,1,2,4] equal to 0 in the following way:
  - Choose [4, 3, 1, 2, 4] and k = 2. Subtract 22 from both numbers. The subarray becomes [0, 3, 1, 2, 0].
  - Choose [0, 3, 1, 2, 0] and k = 0. Subtract 20 from both numbers. The subarray becomes [0, 2, 0, 2, 0].
  - Choose [0, 2, 0, 2, 0] and k = 1. Subtract 21 from both numbers. The subarray becomes [0, 0, 0, 0, 0].

**Example 2:**

**Input:** nums = [1,10,4]
**Output:** 0
**Explanation:** There are no beautiful subarrays in nums.

**Constraints:**

* `1 <= nums.length <= 105`
* `0 <= nums[i] <= 106`

# Approaches
## Brute Force with XOR
This approach directly translates the problem into code by checking every possible contiguous subarray. For each subarray, it calculates the XOR sum of its elements. A subarray is beautiful if and only if its XOR sum is zero. While straightforward, this method is inefficient due to its nested loop structure.
**Time:** O(N^2), where N is the length of the input array `nums`. We have two nested loops, each potentially running up to N times. · **Space:** O(1), as we only use a few variables to store the count and the running XOR sum, regardless of the input size.
**Pros:** Simple to understand and implement.; Requires minimal extra space (O(1)).
**Cons:** The O(N^2) time complexity is too slow for the given constraints (N up to 10^5) and will result in a 'Time Limit Exceeded' error on most platforms.
### Explanation
The fundamental insight is that a subarray can be reduced to all zeros if and only if the XOR sum of all its elements is 0. This is because each operation involves subtracting `2^k` from two numbers, which is equivalent to flipping the `k`-th bit in both. This operation does not change the XOR sum of the subarray. If the final state is all zeros (XOR sum 0), the initial XOR sum must also have been 0.

This brute-force approach iterates through all possible starting points `i` and ending points `j` of a subarray. For each subarray `nums[i...j]`, it computes the XOR sum. If the sum is 0, we count it as a beautiful subarray.

```java
class Solution {
    public long beautifulSubarrays(int[] nums) {
        long count = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            int currentXor = 0;
            for (int j = i; j < n; j++) {
                currentXor ^= nums[j];
                if (currentXor == 0) {
                    count++;
                }
            }
        }
        return count;
    }
}
```
### Algorithm
- Initialize a counter `beautiful_count` to 0.
- Iterate through the array with an index `i` from 0 to `n-1`. This `i` will be the starting index of a subarray.
- Inside this loop, start another loop with an index `j` from `i` to `n-1`. This `j` will be the ending index of the subarray.
- For each subarray `nums[i...j]`, calculate its XOR sum. Maintain a `current_xor` variable, initialized to 0 for each `i`.
- In the inner loop, update `current_xor` by XORing it with `nums[j]`.
- If `current_xor` becomes 0, it signifies that the subarray `nums[i...j]` is beautiful. Increment `beautiful_count`.
- After both loops complete, return `beautiful_count`.

## Prefix XOR and Hash Map
This highly efficient approach solves the problem in linear time by using the concept of prefix XOR sums and a hash map. The problem of finding subarrays with an XOR sum of 0 is cleverly transformed into finding pairs of equal prefix XOR sums. A hash map allows for efficient lookup and storage of these prefix XOR sum frequencies.
**Time:** O(N), where N is the length of `nums`. We perform a single pass through the array, and each hash map operation (get and put) takes O(1) average time. · **Space:** O(N) in the worst case. If all prefix XOR sums are unique, the hash map will store N+1 entries. The keys are integers whose values are bounded.
**Pros:** Extremely efficient with O(N) time complexity, making it suitable for large datasets.; Elegant solution based on a common and powerful pattern for subarray problems involving XOR.
**Cons:** Requires extra space for the hash map, which can be up to O(N) in the worst-case scenario where all prefix XOR sums are distinct.
### Explanation
The core idea remains that a subarray `nums[i...j]` is beautiful if its XOR sum is 0. We can express the XOR sum of `nums[i...j]` using prefix XORs. Let `P[k]` be the XOR sum of `nums[0...k]`. Then the XOR sum of `nums[i...j]` is `P[j] ^ P[i-1]` (with `P[-1]` defined as 0).

We need `P[j] ^ P[i-1] = 0`, which implies `P[j] == P[i-1]`. So, the problem is equivalent to finding the number of pairs of indices `(i-1, j)` such that their prefix XOR sums are equal.

We can achieve this in a single pass. We iterate through the array, maintaining the current prefix XOR sum. We use a hash map to store the frequencies of all prefix XOR sums encountered so far. For each element, we calculate the new prefix XOR. If we have seen this value `k` times before, it means there are `k` starting points that would result in a zero XOR sum subarray ending at the current position. We add `k` to our total count and then update the map with the new prefix XOR sum.

We initialize the map with a prefix XOR of 0 having a count of 1 to correctly handle subarrays that start from the beginning of the array.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public long beautifulSubarrays(int[] nums) {
        // The map will store the frequency of each prefix XOR sum.
        // Key: prefix XOR sum, Value: frequency.
        Map<Integer, Integer> prefixXorCounts = new HashMap<>();
        
        // Initialize with prefix XOR of 0 having a count of 1.
        // This handles subarrays that start from index 0.
        prefixXorCounts.put(0, 1);
        
        long beautifulSubarrayCount = 0;
        int currentXor = 0;
        
        for (int num : nums) {
            // Update the current prefix XOR sum.
            currentXor ^= num;
            
            // If we have seen this currentXor value before, it means
            // there are subarrays ending at the current position
            // with an XOR sum of 0.
            int count = prefixXorCounts.getOrDefault(currentXor, 0);
            beautifulSubarrayCount += count;
            
            // Increment the count for the current prefix XOR sum.
            prefixXorCounts.put(currentXor, count + 1);
        }
        
        return beautifulSubarrayCount;
    }
}
```
### Algorithm
- Initialize a hash map `counts` to store the frequency of prefix XOR sums. Add an initial entry `{0: 1}` to handle subarrays that start from index 0.
- Initialize `result = 0` to count beautiful subarrays and `prefix_xor = 0` to store the running prefix XOR sum.
- Iterate through each `num` in the input array `nums`.
- Update the running prefix XOR: `prefix_xor ^= num`.
- Check if this `prefix_xor` value already exists in the `counts` map. The number of times it has appeared before, say `c`, corresponds to `c` subarrays ending at the current position that have an XOR sum of 0.
- Add this count `c` to the `result`: `result += counts.getOrDefault(prefix_xor, 0)`.
- Update the frequency of the current `prefix_xor` in the map: `counts.put(prefix_xor, counts.getOrDefault(prefix_xor, 0) + 1)`.
- After iterating through all numbers, return `result`.

# Solutions
### Java

```java
class Solution {
public
  long beautifulSubarrays(int[] nums) {
    Map<Integer, Integer> cnt = new HashMap<>();
    cnt.put(0, 1);
    long ans = 0;
    int mask = 0;
    for (int x : nums) {
      mask ^= x;
      ans += cnt.getOrDefault(mask, 0);
      cnt.merge(mask, 1, Integer : : sum);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long beautifulSubarrays(vector<int> &nums) {
    unordered_map<int, int> cnt{{0, 1}};
    long long ans = 0;
    int mask = 0;
    for (int x : nums) {
      mask ^= x;
      ans += cnt[mask];
      ++cnt[mask];
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def beautifulSubarrays(self, nums: List[int]) -> int: cnt = Counter({0: 1}) ans = mask = 0 for x in nums: mask ^= x ans += cnt[mask] cnt[mask] += 1 return ans

```