Count the Number of Beautiful Subarrays solution and explanation
9 more videos on this problem
Count the Number of Beautiful Subarrays || Prefix Xor || Faang Interview QuestionAryan Mittal · 12:25 · 3K views
6317. Count the Number of Beautiful Subarrays - LEETCODE WEEKLY CONTEST 336 (Logic explained)Joyjit Codes · 4:51 · 2K views
Leetcode Weekly Contest 336 | 2588 : Count The Number Of Beautiful Subarrays Solution | In HindiCoding Community | Newton School · 16:25 · 1K views
2588. Count the Number of Beautiful Subarrays | Weekly Contest 336 | C++Priyanshi Porwal · 13:59 · 1K views
Count the Number of Beautiful Subarrays | Weekly Contest 336codingMohan · 19:40 · 1K views
6317. Count the Number of Beautiful Subarrays || Weekly Contest 336Code With U-DAY · 8:23 · 807 views
2588. Count the Number of Beautiful Subarrays (Leetcode Medium)Programming Live with Larry · 11:53 · 766 views
Count the Number of Beautiful Subarrays | Leetcode 2588 | Contest 336Tech Courses · 10:25 · 360 views
Count the Number of Beautiful Subarrays | leetcode Weekly 336 | Leetcode MediumBinaryMagic · 13:34 · 277 views
[Leetcode Weekly 336] 2588. Count the Number of Beautiful Subarrays - Explanation 2Sandeep Kumar · 33:32 · 149 views
The problem
You are given a 0-indexed integer array nums. In one operation, you can:
- Choose two different indices
iandjsuch that0 <= i, j < nums.length. - Choose a non-negative integer
ksuch that thekthbit (0-indexed) in the binary representation ofnums[i]andnums[j]is1. - Subtract
2kfromnums[i]andnums[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] <= 106
Approach overview
Problem 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 1: Prefix XOR and Frequency Counting
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.
def count_beautiful_subarrays(nums):
prefix_xor = {0: 1}
xor = 0
count = 0
for num in nums:
xor ^= num
if xor in prefix_xor:
count += prefix_xor[xor]
prefix_xor[xor] += 1
else:
prefix_xor[xor] = 1
return count
# Example usage
nums = [4, 3, 1, 2, 4]
print(count_beautiful_subarrays(nums)) # Output: 2import java.util.HashMap;
public class BeautifulSubarrays {
public static int countBeautifulSubarrays(int[] nums) {
HashMap<Integer, Integer> prefixXor = new HashMap<>();
prefixXor.put(0, 1);
int xor = 0, count = 0;
for (int num : nums) {
xor ^= num;
count += prefixXor.getOrDefault(xor, 0);
prefixXor.put(xor, prefixXor.getOrDefault(xor, 0) + 1);
}
return count;
}
public static void main(String[] args) {
int[] nums = {4, 3, 1, 2, 4};
System.out.println(countBeautifulSubarrays(nums));
}
}#include <iostream>
#include <unordered_map>
#include <vector>
int countBeautifulSubarrays(const std::vector<int>& nums) {
std::unordered_map<int, int> prefixXor;
prefixXor[0] = 1;
int xor = 0, count = 0;
for (int num : nums) {
xor ^= num;
count += prefixXor[xor];
++prefixXor[xor];
}
return count;
}
int main() {
std::vector<int> nums = {4, 3, 1, 2, 4};
std::cout << countBeautifulSubarrays(nums) << std::endl;
return 0;
}function countBeautifulSubarrays(nums) {
let prefixXor = {0: 1};
let xor = 0, count = 0;
for (let num of nums) {
xor ^= num;
if (prefixXor[xor] !== undefined) {
count += prefixXor[xor];
prefixXor[xor] += 1;
} else {
prefixXor[xor] = 1;
}
}
return count;
}
// Example usage
let nums = [4, 3, 1, 2, 4];
console.log(countBeautifulSubarrays(nums)); // Output: 2using System;
using System.Collections.Generic;
public class BeautifulSubarrays {
public static int CountBeautifulSubarrays(int[] nums) {
var prefixXor = new Dictionary<int, int> { { 0, 1 } };
int xor = 0, count = 0;
foreach (var num in nums) {
xor ^= num;
if (prefixXor.TryGetValue(xor, out int freq)) {
count += freq;
prefixXor[xor] = freq + 1;
} else {
prefixXor[xor] = 1;
}
}
return count;
}
public static void Main(string[] args) {
int[] nums = {4, 3, 1, 2, 4};
Console.WriteLine(CountBeautifulSubarrays(nums));
}
}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.
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.
Approach 2: Prefix XOR + Hash Table
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.
function beautifulSubarrays(nums: number[]): number {
const cnt = new Map();
cnt.set(0, 1);
let ans = 0;
let mask = 0;
for (const x of nums) {
mask ^= x;
ans += cnt.get(mask) || 0;
cnt.set(mask, (cnt.get(mask) || 0) + 1);
}
return ans;
}func beautifulSubarrays(nums []int) (ans int64) {
cnt := map[int]int{0: 1}
mask := 0
for _, x := range nums {
mask ^= x
ans += int64(cnt[mask])
cnt[mask]++
}
return
}use std::collections::HashMap;
impl Solution {
pub fn beautiful_subarrays(nums: Vec<i32>) -> i64 {
let mut cnt = HashMap::new();
cnt.insert(0, 1);
let mut ans = 0;
let mut mask = 0;
for &x in nums.iter() {
mask ^= x;
ans += *cnt.get(&mask).unwrap_or(&0);
*cnt.entry(mask).or_insert(0) += 1;
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Prefix XOR and Frequency Counting | Time Complexity: O(n), where n is the length of |
| Prefix XOR + Hash Table | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Count the Number of Beautiful Subarrays easy or hard?
The problem is rated Medium because it requires recognizing that the allowed operations reduce to a zero-XOR condition. Once that insight is clear, applying the prefix XOR frequency pattern makes the implementation straightforward.
Count the Number of Beautiful Subarrays Python/Java solution
Most implementations maintain a running prefix XOR and a hash map that tracks how often each XOR value has appeared. For every element, update the XOR, add the stored frequency to the result, and increment the map entry. The same logic works in Python, Java, C++, C#, and JavaScript.
How to solve Count the Number of Beautiful Subarrays in O(n)?
Maintain a running prefix XOR while iterating through the array. Store frequencies of each prefix XOR in a hash map. For each new prefix value, add the number of times it has appeared before to the answer, because equal prefix XOR values form a subarray with XOR equal to zero.
What is the best approach for Count the Number of Beautiful Subarrays?
The best approach uses prefix XOR combined with a hash map to count frequencies of previously seen XOR values. If the same prefix XOR appears twice, the subarray between those indices has XOR equal to zero, which satisfies the beautiful condition. This solution runs in O(n) time with O(n) extra space.
Is Count the Number of Beautiful Subarrays asked at Google/Amazon/Meta?
Problems based on prefix XOR and zero-XOR subarrays frequently appear in interviews at companies like Google, Amazon, and Meta. Variants such as counting subarrays with XOR equal to a target or zero are common interview patterns.
What data structure is used in Count the Number of Beautiful Subarrays?
The main data structure is a hash map (dictionary) that stores frequencies of prefix XOR values. The algorithm also relies on bit manipulation through XOR operations and a prefix accumulation technique.
What is the time complexity of Count the Number of Beautiful Subarrays?
The optimal prefix XOR and hash map approach runs in O(n) time because the array is scanned once and each hash map operation is O(1) on average. The brute force approach checks all subarrays and takes O(n^2) time.