Skip to content

2588. Count the Number of Beautiful Subarrays 👍

  • Time:
  • Space: 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
 public:
  long long beautifulSubarrays(vector<int>& nums) {
    // A subarray is beautiful if xor(subarray) = 0.
    long ans = 0;
    int prefix = 0;
    unordered_map<int, int> prefixCount{{0, 1}};

    for (const int num : nums) {
      prefix ^= num;
      ans += prefixCount[prefix]++;
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
  public long beautifulSubarrays(int[] nums) {
    // A subarray is beautiful if xor(subarray) = 0.
    long ans = 0;
    int prefix = 0;
    Map<Integer, Integer> prefixCount = new HashMap<>();
    prefixCount.put(0, 1);

    for (final int num : nums) {
      prefix ^= num;
      ans += prefixCount.getOrDefault(prefix, 0);
      prefixCount.merge(prefix, 1, Integer::sum);
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
  def beautifulSubarrays(self, nums: list[int]) -> int:
    # A subarray is beautiful if xor(subarray) = 0.
    ans = 0
    prefix = 0
    prefixCount = collections.Counter({0: 1})

    for num in nums:
      prefix ^= num
      ans += prefixCount[prefix]
      prefixCount[prefix] += 1

    return ans