Problem Description
Given an array of non-negative integers, a subarray is called beautiful if it is possible to reduce all its elements to 0 by repeatedly choosing two different indices and subtracting 2^k from both elements at positions i and j (for some non-negative integer k) provided the kth bit in both numbers is 1. Determine the number of beautiful (contiguous) subarrays in the given array.
Key Insights
- The operation subtracts 2^k from two numbers only if the kth bit is set in both. This means that for every binary bit position, we can only remove bits in pairs.
- A subarray can be reduced to zero if and only if, for every bit, the count of ones in that bit position is even.
- Observing that parity (even/odd) of bit counts is equivalent to computing the XOR of the subarray, a beautiful subarray must satisfy that its XOR equals 0.
- Thus, the problem reduces to counting subarrays with a cumulative XOR of 0.
- A prefix sum (or prefix XOR) technique with a hashmap can efficiently count subarrays that have the required property.
Space and Time Complexity
Time Complexity: O(n), where n is the number of elements in the array.
Space Complexity: O(n) in the worst case, for storing counts of prefix XOR values in a hashmap.
Solution
The solution uses a prefix XOR method. Define prefixXOR such that prefixXOR[i] is the XOR of nums[0..i]. A subarray nums[i+1..j] has XOR equal to prefixXOR[j] XOR prefixXOR[i]. For the subarray to have XOR 0, it must be that prefixXOR[j] equals prefixXOR[i]. Additionally, if the prefixXOR itself is zero at a given index, the subarray from the beginning to that index is beautiful.
By maintaining a hashmap that maps each prefixXOR value to its count, we can increment the result by the count each time we see the same prefixXOR again. This efficiently counts all beautiful subarrays in one pass.