2588. Count the Number of Beautiful Subarrays

MediumBit ManipulationArrayHash TablePrefix Sum
Leetcode Link

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which data structure is used to implement priority queue?

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:

  1. Initialize a Counter named cnt with a starting count of 1 for a prefix XOR of 0 to handle the case where a subarray starting from index 0 can be made beautiful.
  2. Initialize variables ans to store the count of beautiful subarrays and mask to keep track of the current prefix XOR value, both set initially to 0.
  3. Iterate through each element x in the input array nums. a. XOR the current element x with mask to update mask 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 current mask from the cnt to ans. 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 current mask in cnt by 1 to account for the new occurrence of this XOR value.
  4. Continue this process until the end of the array.
  5. 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Example 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:

  1. Initialize a Counter, cnt, with a count of 1 for a prefix XOR of 0 and set ans = 0 and mask = 0.
  2. Starting with the first element:
    • mask XOR 3 = 3 (binary 011). We update ans by adding the occurrence of mask (which is 0, as 3 has not been encountered before), and then increment the count of mask = 3 in cnt.
  3. Moving to the second element:
    • mask (which was 3) XOR 4 = 7 (binary 111). We update ans by adding the occurrence of mask = 7 (again 0), and increment the count of mask in cnt.
  4. For the third element:
    • mask = 7 XOR 5 = 2 (binary 010). We update ans with the count of mask = 2 (which is 0) and increment the count of mask in cnt.
  5. For the fourth element:
    • mask = 2 XOR 2 = 0. This is interesting because the prefix XOR is now 0, meaning a subarray from the start can be made beautiful. We update ans with the count of mask (which is 1, from the initial cnt), and increment the count of mask = 0 in cnt.
  6. For the fifth element:
    • mask = 0 XOR 4 = 4. We update ans by adding the occurrence of mask = 4 (which is 0), and increment the count of mask in cnt.

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
Not Sure What to Study? Take the 2-min Quiz：

A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".

What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?

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.

Fast Track Your Learning with Our Quick Skills Quiz:

Breadth first search can be used to find the shortest path between two nodes in a directed graph.

Recommended Readings

Prefix Sum

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 - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

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

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫