Count the Number of Beautiful Subarrays — Problem & Solution
Count the Number of Beautiful Subarrays solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Count the Number of Beautiful Subarrays is a medium coding problem on arrays, hash table and bit manipulation, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Bit Manipulation, Prefix Sum
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
An operation on an array picks two different indices i and j and a bit position b such that bit b is set in both arr[i] and arr[j], then subtracts 2^b from both of them.
An array is beautiful if some sequence of operations (possibly none) turns every element into 0. Return the number of beautiful subarrays (contiguous, non-empty) of nums.
Note: the original problem allows 10^5 elements and returns a 64-bit count; here nums.length <= 5 * 10^4, so the answer always fits in a 32-bit integer.
Example 1
Input: nums = [5,1,4,7,7]
Output: 3
Explanation: `[5,1,4]` (bit 0 from 5 and 1, then bit 2 from 4 and 4), `[7,7]`, and the whole array.
Example 2
Input: nums = [1,10,4]
Output: 0
Example 3
Input: nums = [0]
Output: 1
Explanation: Already all zeros.
Constraints
1 <= nums.length <= 5 * 10^40 <= nums[i] <= 10^6
Hints for Count the Number of Beautiful Subarrays
Hint 1
Each operation clears one bit in exactly two elements. What does that say about how many elements have a given bit set?
Hint 2
A subarray is beautiful exactly when every bit is set in an even number of its elements — i.e. its XOR is 0.
Hint 3
Count pairs of equal prefix XORs with a hash map (including the empty prefix 0).
How to solve Count the Number of Beautiful Subarrays
An operation removes bit b from exactly two elements, so it preserves the parity of how many elements have bit b. Hence a subarray can be zeroed if and only if its XOR is 0, and counting zero-XOR subarrays is a prefix-XOR pair count.
Approach
- Keep
cnt, a map from prefix XOR value to how often it has appeared, starting withcnt[0] = 1. - Sweep the array maintaining
x= XOR of the prefix so far. - Add
cnt[x]to the answer (each earlier equal prefix starts a zero-XOR subarray ending here), then incrementcnt[x]. - Return the total.
Why it works
Necessity: parity of each bit's count is invariant, and all-zero has even counts. Sufficiency: if every bit has an even count, pair up the elements holding each bit and clear it pairwise, bit by bit. Finally XOR(nums[l..r]) = P[r+1] ^ P[l], which is 0 exactly when the two prefix XORs are equal.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Seed the map with the empty prefix (
cnt[0] = 1), or subarrays starting at index 0 are missed. - Zeros alone are beautiful (
[0]counts). - With the original limits the count needs 64 bits.
Reference solution
Python
from typing import List
def beautifulSubarrays(nums: List[int]) -> int:
cnt = {0: 1}
x = 0
total = 0
for v in nums:
x ^= v
c = cnt.get(x, 0)
total += c
cnt[x] = c + 1
return totalJava
public static int beautifulSubarrays(int[] nums) {
Map<Integer, Integer> cnt = new HashMap<>();
cnt.put(0, 1);
int x = 0;
long total = 0;
for (int v : nums) {
x ^= v;
int c = cnt.getOrDefault(x, 0);
total += c;
cnt.put(x, c + 1);
}
return (int) total;
}C++
int beautifulSubarrays(vector<int>& nums) {
unordered_map<int, int> cnt;
cnt[0] = 1;
int x = 0;
long long total = 0;
for (int v : nums) {
x ^= v;
total += cnt[x];
cnt[x]++;
}
return (int)total;
}JavaScript
var beautifulSubarrays = function(nums) {
var cnt = new Map();
cnt.set(0, 1);
var x = 0, total = 0;
for (var i = 0; i < nums.length; i++) {
x ^= nums[i];
var c = cnt.get(x) || 0;
total += c;
cnt.set(x, c + 1);
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets