Watch 10 video solutions for Count the Number of Beautiful Subarrays, a medium level problem involving Array, Hash Table, Bit Manipulation. This walkthrough by Aryan Mittal has 3,442 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |