Count the Number of Beautiful Subarrays

Medium
1169.

Count the Number of Beautiful Subarrays

Count the Number of Beautiful Subarrays is a medium coding problem on arrays, hash table and bit manipulation, asked in Amazon and Google interviews.

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^4
  • 0 <= nums[i] <= 10^6
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var beautifulSubarrays = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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^4
  • 0 <= nums[i] <= 10^6

Hints for Count the Number of Beautiful Subarrays

  1. Hint 1

    Each operation clears one bit in exactly two elements. What does that say about how many elements have a given bit set?

  2. 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.

  3. 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

  1. Keep cnt, a map from prefix XOR value to how often it has appeared, starting with cnt[0] = 1.
  2. Sweep the array maintaining x = XOR of the prefix so far.
  3. Add cnt[x] to the answer (each earlier equal prefix starts a zero-XOR subarray ending here), then increment cnt[x].
  4. 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 total

Java

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