Count the Number of Beautiful Subarrays

Med

#2368Time: 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.

Patterns

Bit Manipulation Prefix Sum

Data structures

Array Hash Table

Prompt

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 k^th bit (0-indexed) in the binary representation of nums[i] and nums[j] is 1.
Subtract 2^k 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 <= 10⁵
0 <= nums[i] <= 10⁶

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1class Solution {2    public long beautifulSubarrays(int[] nums) {3        long count = 0;4        int n = nums.length;5        for (int i = 0; i < n; i++) {6            int currentXor = 0;7            for (int j = i; j < n; j++) {8                currentXor ^= nums[j];9                if (currentXor == 0) {10                    count++;11                }12            }13        }14        return count;15    }16}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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.

1import java.util.HashMap;2import java.util.Map;3 4class Solution {5    public long beautifulSubarrays(int[] nums) {6        // The map will store the frequency of each prefix XOR sum.7        // Key: prefix XOR sum, Value: frequency.8        Map<Integer, Integer> prefixXorCounts = new HashMap<>();9        10        // Initialize with prefix XOR of 0 having a count of 1.11        // This handles subarrays that start from index 0.12        prefixXorCounts.put(0, 1);13        14        long beautifulSubarrayCount = 0;15        int currentXor = 0;16        17        for (int num : nums) {18            // Update the current prefix XOR sum.19            currentXor ^= num;20            21            // If we have seen this currentXor value before, it means22            // there are subarrays ending at the current position23            // with an XOR sum of 0.24            int count = prefixXorCounts.getOrDefault(currentXor, 0);25            beautifulSubarrayCount += count;26            27            // Increment the count for the current prefix XOR sum.28            prefixXorCounts.put(currentXor, count + 1);29        }30        31        return beautifulSubarrayCount;32    }33}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  long beautifulSubarrays(int[] nums) {4    Map<Integer, Integer> cnt = new HashMap<>();5    cnt.put(0, 1);6    long ans = 0;7    int mask = 0;8    for (int x : nums) {9      mask ^= x;10      ans += cnt.getOrDefault(mask, 0);11      cnt.merge(mask, 1, Integer : : sum);12    }13    return ans;14  }15}

1class Solution {2public:3  long long beautifulSubarrays(vector<int> &nums) {4    unordered_map<int, int> cnt{{0, 1}};5    long long ans = 0;6    int mask = 0;7    for (int x : nums) {8      mask ^= x;9      ans += cnt[mask];10      ++cnt[mask];11    }12    return ans;13  }14};

1class Solution:2    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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem