Problem

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 ofbeautiful subarrays in the array nums.

A subarray is a contiguous non-empty sequence of elements within an array.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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

1
2
3

Input: nums = [1,10,4]
Output: 0
Explanation: There are no beautiful subarrays in nums.

Constraints

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] <= 10^6

Solution

Method 1 – Prefix XOR and Hash Map

Intuition

A subarray is beautiful if we can make all its elements zero using the allowed operation. This is possible if, for every bit position, the count of set bits in the subarray is even (i.e., the XOR of all elements in the subarray is zero). Thus, the problem reduces to counting the number of subarrays whose XOR is zero.

Approach

  1. Compute the prefix XOR for the array.
  2. Use a hash map to count the frequency of each prefix XOR value.
  3. For each prefix XOR value, the number of pairs of indices with the same value gives the number of beautiful subarrays.
  4. For each prefix XOR value with count c, the number of subarrays is c * (c - 1) // 2.
  5. Return the total count.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    long long beautifulSubarrays(vector<int>& nums) {
        unordered_map<int, long long> cnt;
        cnt[0] = 1;
        int x = 0;
        long long ans = 0;
        for (int a : nums) {
            x ^= a;
            ans += cnt[x];
            cnt[x]++;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

type Solution struct{}
func (Solution) BeautifulSubarrays(nums []int) int64 {
    cnt := map[int]int64{0: 1}
    x, ans := 0, int64(0)
    for _, a := range nums {
        x ^= a
        ans += cnt[x]
        cnt[x]++
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public long beautifulSubarrays(int[] nums) {
        Map<Integer, Long> cnt = new HashMap<>();
        cnt.put(0, 1L);
        int x = 0;
        long ans = 0;
        for (int a : nums) {
            x ^= a;
            ans += cnt.getOrDefault(x, 0L);
            cnt.put(x, cnt.getOrDefault(x, 0L) + 1);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    fun beautifulSubarrays(nums: IntArray): Long {
        val cnt = mutableMapOf(0 to 1L)
        var x = 0
        var ans = 0L
        for (a in nums) {
            x = x xor a
            ans += cnt.getOrDefault(x, 0L)
            cnt[x] = cnt.getOrDefault(x, 0L) + 1
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def beautifulSubarrays(self, nums: list[int]) -> int:
        from collections import defaultdict
        cnt = defaultdict(int)
        cnt[0] = 1
        x = 0
        ans = 0
        for a in nums:
            x ^= a
            ans += cnt[x]
            cnt[x] += 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

use std::collections::HashMap;
impl Solution {
    pub fn beautiful_subarrays(nums: Vec<i32>) -> i64 {
        let mut cnt = HashMap::new();
        cnt.insert(0, 1i64);
        let mut x = 0;
        let mut ans = 0i64;
        for &a in &nums {
            x ^= a;
            ans += *cnt.get(&x).unwrap_or(&0);
            *cnt.entry(x).or_insert(0) += 1;
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    beautifulSubarrays(nums: number[]): number {
        const cnt = new Map<number, number>();
        cnt.set(0, 1);
        let x = 0, ans = 0;
        for (const a of nums) {
            x ^= a;
            ans += cnt.get(x) ?? 0;
            cnt.set(x, (cnt.get(x) ?? 0) + 1);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of nums, since we scan the array once.
  • 🧺 Space complexity: O(n), for the hash map storing prefix XOR counts.