Skip to content

Bit XOR

Table of Contents

1486. XOR Operation in an Array

1720. Decode XORed Array

2433. Find The Original Array of Prefix Xor

1310. XOR Queries of a Subarray

2683. Neighboring Bitwise XOR

1829. Maximum XOR for Each Query

2997. Minimum Number of Operations to Make Array XOR Equal to K

1442. Count Triplets That Can Form Two Arrays of Equal XOR

  • LeetCode | 力扣

  • Tags: Array, Hash Table, Math, Bit Manipulation, Prefix Sum

2429. Minimize XOR

2527. Find Xor-Beauty of Array

2317. Maximum XOR After Operations

2588. Count the Number of Beautiful Subarrays

  • LeetCode | 力扣

  • Tags: Array, Hash Table, Bit Manipulation, Prefix Sum

from collections import defaultdict
from typing import List


class Solution:
    def beautifulSubarrays(self, nums: List[int]) -> int:
        """Prefix XOR + HashMap: O(n) time, O(n) space.
        A subarray XORs to 0 iff its prefix XOR equals
        a previously seen prefix XOR.
        """
        res, prefix = 0, 0
        cnt = defaultdict(int)
        cnt[0] = 1
        for x in nums:
            prefix ^= x
            res += cnt[prefix]
            cnt[prefix] += 1
        return res


def test_beautiful_subarrays():
    s = Solution()
    assert s.beautifulSubarrays([4, 3, 1, 2, 4]) == 2
    assert s.beautifulSubarrays([1, 10, 4]) == 0
    assert s.beautifulSubarrays([0]) == 1

2564. Substring XOR Queries

1734. Decode XORed Permutation

2857. Count Pairs of Points With Distance k

1803. Count Pairs With XOR in a Range

3215. Count Triplets with Even XOR Set Bits II 👑