You are given a 0-indexed integer array nums. In one operation, you can:
i and j such that 0 <= i, j < nums.length.k such that the kth bit (0-indexed) in the binary representation of nums[i] and nums[j] is 1.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.
Return the number of beautiful subarrays in the array nums.
A subarray is a contiguous non-empty sequence of elements within an array.
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 <= 1050 <= nums[i] <= 106Problem Overview: You are given an integer array and need to count subarrays that can be transformed into all zeros using a specific operation that removes matching highest set bits from two elements. A subarray is considered beautiful if such operations can eventually reduce every value in that subarray to zero.
The key observation is that the operation effectively cancels bits in pairs. For a subarray to become all zeros, every bit position must appear an even number of times across the subarray. This condition is equivalent to saying the XOR of all numbers in the subarray equals 0.
Approach 1: Brute Force Subarray XOR Check (O(n²) time, O(1) space)
Enumerate every possible subarray using two nested loops. Maintain a running XOR while extending the subarray from index i to j. Each time the running XOR becomes 0, increment the count because the current subarray satisfies the "beautiful" condition. This approach directly checks the XOR property but examines all O(n²) subarrays, which becomes slow for large inputs. It works for small constraints and helps build intuition about why XOR zero is the target condition.
Approach 2: Prefix XOR and Frequency Counting (O(n) time, O(n) space)
Compute a running prefix XOR while scanning the array once. If two prefix XOR values are equal at indices i and j, the subarray between them has XOR 0. Use a hash map to track how many times each prefix XOR has appeared so far. For each element, update the prefix XOR, add the current frequency of that value to the answer, then increment its count in the map. This converts the problem into counting equal prefix XOR pairs.
This technique is a standard pattern combining prefix sum-style accumulation with a hash table for frequency tracking. XOR works particularly well because identical prefixes cancel out: prefix[j] ^ prefix[i] = 0. Bit parity across the subarray is automatically enforced, which aligns with the allowed bit operations described in the problem.
Recommended for interviews: Interviewers expect the prefix XOR + hash map solution. Starting with the brute force approach shows you understand the XOR condition, but recognizing that equal prefix XOR values form zero-XOR subarrays demonstrates strong knowledge of bit manipulation and prefix techniques. The optimal solution runs in linear time and is the standard pattern used in many XOR-subarray problems.
To find the number of beautiful subarrays, we'll utilize the properties of XOR. The idea is to calculate the prefix XOR for all the elements and utilize a hashmap (or dictionary) to count how often each prefix XOR appears. A subarray is beautiful if the XOR of the integers in it is zero. By using prefix XORs, the XOR of any subarray from i to j can be calculated. By finding matching prefix XORs, we can count how many subarrays XOR to zero.
The function initializes a dictionary prefix_xor with 0 mapping to 1 to handle the subarrays directly starting from the beginning. As we iterate through the array, we compute the running XOR in the variable xor. For each element in nums, we update the count of beautiful subarrays if the current xor exists in prefix_xor, incrementing the count appropriately. The dictionary prefix_xor is also updated to include the current xor state.
Python
Java
C++
C#
JavaScript
Time Complexity: O(n), where n is the length of nums as we process each number once.
Space Complexity: O(n), in the worst case when all prefix XORs are distinct.
We observe that a subarray can become an array of all 0s if and only if the number of 1s on each binary bit of all elements in the subarray is even.
If there exist indices i and j such that i \lt j and the subarrays nums[0,..,i] and nums[0,..,j] have the same parity of the number of 1s on each binary bit, then we can turn the subarray nums[i + 1,..,j] into an array of all 0s.
Therefore, we can use the prefix XOR method and a hash table cnt to count the occurrences of each prefix XOR value. We traverse the array, for each element x, we calculate its prefix XOR value mask, then add the number of occurrences of mask to the answer. Then, we increase the number of occurrences of mask by 1.
Finally, we return the answer.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array nums.
| Approach | Complexity |
|---|---|
| Prefix XOR and Frequency Counting | Time Complexity: O(n), where n is the length of |
| Prefix XOR + Hash Table | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subarray XOR | O(n²) | O(1) | Useful for understanding the XOR property or when constraints are very small |
| Prefix XOR + Hash Map Frequency | O(n) | O(n) | Optimal solution for large arrays; standard interview approach |
Count the Number of Beautiful Subarrays || Prefix Xor || Faang Interview Question • Aryan Mittal • 3,442 views views
Watch 9 more video solutions →Practice Count the Number of Beautiful Subarrays with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor