Count the number of beautiful subarrays

Array Hash Table Bit Manipulation Prefix Sum

53.4% acceptance

Feb 25, 2026

560

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 (including zero). Return the number of beautiful subarrays in the array nums. A subarray is a contiguous non-empty sequence of elements within an array. Note: Subarrays where all elements are initially 0 are considered beautiful, as no operation is needed.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

use std::collections::HashMap;
impl Solution {
  pub fn beautiful_subarrays(nums: Vec<i32>) -> i64 {
    // A subarray is beautiful if XOR of all its elements equals 0
    // (because any bit that appears an odd number of times cannot be cancelled).
    // Use prefix XOR + HashMap: count pairs (i,j) where prefix[i] == prefix[j].
    let mut count: HashMap<i32, i64> = HashMap::new();
    count.insert(0, 1);
    let mut prefix = 0i32;
    let mut ans = 0i64;
    for x in nums {
      prefix ^= x;
      let e = count.entry(prefix).or_insert(0);
      ans += *e;
      *e += 1;
    }
    ans
  }
}