2588. Count the Number of Beautiful Subarrays
Problem Description
Given an array nums
, the task is to count the number of "beautiful subarrays". A subarray is considered beautiful if you can perform a series of operations that make all its elements equal to zero. In one operation, you can pick any two different indices i
and j
and a non-negative integer k
. The kth
bit in the binary representation of both nums[i]
and nums[j]
should be a 1
. You then subtract 2^k
from both nums[i]
and nums[j]
. A subarray, in this context, is defined as a contiguous non-empty sequence of elements within the array nums
.
Intuition
The intuition behind the solution involves understanding the properties of XOR and bit manipulation. The important observation is that a subarray can be made all zeros if, for each bit position, the total count of 1s is even. This is because the defined operation allows us to simultaneously subtract the value of that bit position from two numbers with a 1 in that same position, effectively reducing the count of 1s by two.
To track the number of 1s at each bit position across subarrays, we use the concept of prefix XOR. When we XOR a number with itself, it results in zero, and XORing a number with zero results in the original number. By applying prefix XOR as we traverse the array, we can determine if there is an equal number of 1s in each bit position between two indices: if the prefix XOR at two different indices is the same, then the subarray between them can be turned into an array of zeros.
We utilize a hash table to store the counts of each prefix XOR encountered. For every element in the array, we calculate the prefix XOR up to that element (mask
) and check how many times this mask
has occurred before (using the counter cnt
). These counts correspond to the number of subarrays ending at the current index that can be converted into beautiful arrays. Each time we visit an element, we update the count for its corresponding mask
. The sum of all these counts gives us the number of beautiful subarrays in the original array.
Learn more about Prefix Sum patterns.
Solution Approach
The solution approach leverages a hash table to store the occurrence count of each prefix XOR value encountered while traversing the array. Specifically, we use Python's Counter
data structure for this purpose. The steps can be broken down into the following algorithm:
- Initialize a
Counter
namedcnt
with a starting count of1
for a prefix XOR of0
to handle the case where a subarray starting from index0
can be made beautiful. - Initialize variables
ans
to store the count of beautiful subarrays andmask
to keep track of the current prefix XOR value, both set initially to0
. - Iterate through each element
x
in the input arraynums
. a. XOR the current elementx
withmask
to updatemask
to the new prefix XOR value (this keeps track of the cumulative XOR from the start of the array to the current index). b. Add the count of the currentmask
from thecnt
toans
. This total represents the number of previous subarrays that had the same XOR value, which means the subarray from the end of any of those to the current index can be made beautiful. c. Increase the count of the currentmask
incnt
by 1 to account for the new occurrence of this XOR value. - Continue this process until the end of the array.
- After completing the iteration,
ans
contains the total count of beautiful subarrays.
This approach is efficient since it only needs to pass through the array once, with computations at each index being constant time due to the use of XOR and hash table lookups. Thus, the overall time complexity is O(n), where n is the number of elements in the input array nums
.
The key to this solution is the use of prefix XOR to effectively identify subarrays that can be transformed to zero, based on the property that the XOR of any number with itself is zero and XOR with zero preserves the number. By applying this logic, and by keeping track of the number of occurrences of each XOR value seen so far, we can count all beautiful subarrays without needing to examine each potential subarray explicitly.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's assume we have an array nums = [3, 4, 5, 2, 4]
, and we want to apply the solution approach to count the number of beautiful subarrays. Here's a step-by-step walkthrough:
- Initialize a
Counter
,cnt
, with a count of1
for a prefix XOR of0
and setans = 0
andmask = 0
. - Starting with the first element:
mask
XOR3
=3
(binary011
). We updateans
by adding the occurrence ofmask
(which is0
, as3
has not been encountered before), and then increment the count ofmask = 3
incnt
.
- Moving to the second element:
mask
(which was3
) XOR4
=7
(binary111
). We updateans
by adding the occurrence ofmask = 7
(again0
), and increment the count ofmask
incnt
.
- For the third element:
mask = 7
XOR5
=2
(binary010
). We updateans
with the count ofmask = 2
(which is0
) and increment the count ofmask
incnt
.
- For the fourth element:
mask = 2
XOR2
=0
. This is interesting because the prefix XOR is now0
, meaning a subarray from the start can be made beautiful. We updateans
with the count ofmask
(which is1
, from the initialcnt
), and increment the count ofmask = 0
incnt
.
- For the fifth element:
mask = 0
XOR4
=4
. We updateans
by adding the occurrence ofmask = 4
(which is0
), and increment the count ofmask
incnt
.
The counts in the Counter
at the end of this traversal are cnt = {0: 2, 3: 1, 7: 1, 2: 1, 4: 1}
, and ans = 1
, representing the single beautiful subarray [3, 4, 5, 2]
which can be made all zeros by the series of operations specified.
This small example demonstrates how the solution works. As we traverse nums
, we cumulatively XOR the numbers and use a hash table to keep track of how many times we've seen each XOR result. When we encounter the same XOR result again, it means we have found a subarray that can be made beautiful. The final count of beautiful subarrays in this example is 1
.
Solution Implementation
1from collections import Counter
2
3class Solution:
4 def beautifulSubarrays(self, nums: List[int]) -> int:
5 # Initialize a counter to keep track of the frequency of XOR accumulative sums.
6 # The counter is initialized with the accumulative sum '0' having a count of 1.
7 xor_freq_counter = Counter({0: 1})
8
9 # Initialize 'ans' to count the number of beautiful subarrays.
10 # Initialize 'xor_accumulative' to store the accumulative XOR sum.
11 ans, xor_accumulative = 0, 0
12
13 # Iterate over the elements in nums.
14 for num in nums:
15 # Update the accumulative XOR sum with the current number.
16 xor_accumulative ^= num
17
18 # If the XOR sum has been seen before, it means there is a subarray
19 # with an even number of 1's, so add the previous count to 'ans'.
20 ans += xor_freq_counter[xor_accumulative]
21
22 # Update the frequency counter for the current XOR accumulative sum.
23 xor_freq_counter[xor_accumulative] += 1
24
25 # Return the total count of beautiful subarrays.
26 return ans
27
28# Note: The List type requires importing from the typing module in Python 3.
29# from typing import List
30
1class Solution {
2 public long beautifulSubarrays(int[] nums) {
3 // Map to store the count of each prefix XOR value encountered
4 Map<Integer, Integer> prefixXorCount = new HashMap<>();
5
6 // Initialize the map with the base case where there is no prefix (XOR value is 0)
7 prefixXorCount.put(0, 1);
8
9 // To keep track of the total number of beautiful subarrays
10 long totalCount = 0;
11
12 // To store the XOR of all numbers from the start of the array to the current index
13 int currentXor = 0;
14
15 for (int num : nums) {
16 // Update the currentXor with the XOR of the current number
17 currentXor ^= num;
18
19 // Increment the totalCount by the number of times this XOR value has been seen before
20 totalCount += prefixXorCount.getOrDefault(currentXor, 0);
21
22 // Increment the count of the currentXor value in our prefixXorCount map
23 prefixXorCount.merge(currentXor, 1, Integer::sum);
24 }
25
26 // Return the total number of beautiful subarrays
27 return totalCount;
28 }
29}
30
1#include <vector>
2#include <unordered_map>
3using namespace std;
4
5class Solution {
6public:
7 long long beautifulSubarrays(vector<int>& nums) {
8 // This unordered_map will store the frequency of each XOR value encountered.
9 unordered_map<int, int> countMap{{0, 1}};
10 // This variable will store the total number of beautiful subarrays.
11 long long totalBeautifulSubarrays = 0;
12 // The mask will hold the cumulative XOR value as we iterate through the vector.
13 int cumulativeXor = 0;
14
15 // Iterate over the vector to calculate the beautiful subarrays.
16 for (int num : nums) {
17 // Compute the cumulative XOR up to the current number.
18 cumulativeXor ^= num;
19 // Add the current count of the cumulativeXor to our answer, as any previous occurrence
20 // of the same cumulativeXor indicates a subarray with an even number of each integer.
21 totalBeautifulSubarrays += countMap[cumulativeXor];
22 // Increase the count of the cumulativeXor in our map.
23 ++countMap[cumulativeXor];
24 }
25 // Return the final count of beautiful subarrays.
26 return totalBeautifulSubarrays;
27 }
28};
29
1// Function to count the number of beautiful subarrays in an array of numbers.
2// A beautiful subarray is defined as the one where the bitwise XOR of all elements is 0.
3function beautifulSubarrays(nums: number[]): number {
4 // Initialize a Map to store the frequency of XORed results.
5 const xorFrequency = new Map<number, number>();
6 xorFrequency.set(0, 1); // Set the frequency for 0 as 1 to account for the initial state.
7
8 // Variable to store the total count of beautiful subarrays.
9 let totalBeautifulSubarrays = 0;
10
11 // Variable to keep track of the cumulative XOR result as we iterate through the array.
12 let cumulativeXor = 0;
13
14 // Loop through each number in the given array.
15 for (const num of nums) {
16 // Update the cumulative XOR.
17 cumulativeXor ^= num;
18
19 // If the current cumulative XOR result has been seen before, add its frequency to the total count.
20 totalBeautifulSubarrays += xorFrequency.get(cumulativeXor) || 0;
21
22 // Update the frequency of the current cumulative XOR result in the map.
23 // If it doesn't exist, initialize it with 0 and then add 1.
24 xorFrequency.set(cumulativeXor, (xorFrequency.get(cumulativeXor) || 0) + 1);
25 }
26
27 // Return the total count of beautiful subarrays found.
28 return totalBeautifulSubarrays;
29}
30
Time and Space Complexity
The time complexity of the code is O(n)
where n
is the length of the array nums
. This is because the code iterates through the array exactly once with a sequence of O(1)
operations within the loop, such as XOR operation, dictionary lookup, and dictionary update.
The space complexity of the code is also O(n)
because the Counter
object cnt
potentially stores a unique entry for every prefix XOR result in the nums
array. In the worst case, this could be as many as n
unique entries, if every prefix XOR results in a different value.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following problems can be solved with backtracking (select multiple)
Recommended Readings
Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!