Skip to main content
Talentd

Count the Number of Beautiful Subarrays - Solution & Explanation

MediumArrayHash TableBit ManipulationPrefix Sum15 min read
Practice this problem

Problem Statement

You are given a 0-indexed integer array nums. In one operation, you can:

  • Choose two different indices i and j such that 0 <= i, j < nums.length.
  • Choose a non-negative integer k such that the kth bit (0-indexed) in the binary representation of nums[i] and nums[j] is 1.
  • Subtract 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 <= 105
  • 0 <= 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.

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.

Code

PythonJavaC++C#JavaScript

Python

Java

C++

C#

JavaScript

Complexity

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.

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Prefix XOR and Frequency Counting

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.

Prefix XOR + Hash Table—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Subarray XORO(n²)O(1)Useful for understanding the XOR property or when constraints are very small
Prefix XOR + Hash Map FrequencyO(n)O(n)Optimal solution for large arrays; standard interview approach

Video Solution

Count the Number of Beautiful Subarrays || Prefix Xor || Faang Interview Question • Aryan Mittal • 3,597 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Count the Number of Beautiful Subarrays with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count the Number of Ideal Arrays

Next

Maximum XOR for Each Query