This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

This is 1442 on LeetCode. The number of triples that form two xor equal arrays, of medium difficulty.

Tag: “math”, “prefix and”

I give you an integer array arr.

We now need to fetch three subscripts I, j, and k from the array, where (0 <= I < j <= k < arr.length).

A and B are defined as follows:

  • a = arr[i] ^ arr[i + 1] ^ … ^ arr[j – 1]
  • b = arr[j] ^ arr[j + 1] ^ … ^ arr[k]

Note: ^ represents a bitwise xor operation.

Return the number of triples (I, j, k) that make a == b true.

Example 1:

Input: arr =,3,1,6,7 [2] output: 4: meet the question of triples (0), (0,2,2), (2 and 4) and (2),4,4Copy the code

Example 2:

Input: arr = [1,1,1,1,1] output: 10Copy the code

Example 3:

Input: arr = [2,3] output: 0Copy the code

Example 4:

Arr = [1,3,5,7,9] output: 3Copy the code

Example 5:

Input: arr = [7,11,12,9,5,2,7,17,22] output: 8Copy the code

Tip:

  • 1 <= arr.length <= 300
  • 1 <= arr[i] <=
    1 0 8 10^8

Fundamental analysis

The data range is 10210^2102, and the triplet contains subscripts III, JJJ, and KKK, so O(n4)O(n^4)O(n4) n4 by “enumerating subscripts” and “calculating xOR each time through the loop” is ignored.

For those of you who have done xOR queries for 1310. Subarrays, it is not difficult to imagine that we can use “tree array” or “prefix xor” to optimize our “xOR result for each loop” process.

Since no modification operation is involved, prefix XOR is preferred. So this is O(n3)O(n^3)O(n3), ok.

The prefix xor

Preprocesses the prefix xor array and enumerates the subscripts of triples.

In essence, it makes use of the inclusive exclusion principle of sets (interval results). But prefix and need to use “subtraction (inverse operation)” to do exclusion, and prefix xor use “the same value xor result is
0 0 (The xor of the even number is
0 0 ) “feature to implement inclusive exclusion.

Code:

class Solution {
    public int countTriplets(int[] arr) {
        int n = arr.length;
        int[] sum = new int[n + 1];
        for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] ^ arr[i - 1];
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                for (int k = j; k <= n; k++) {
                    int a = sum[j - 1] ^ sum[i - 1];
                    int b = sum[k] ^ sum[j - 1];
                    if(a == b) ans++; }}}returnans; }}Copy the code
  • Time complexity: O(n3)O(n^3)O(n3)
  • Space complexity: O(n)O(n)O(n)

Prefix xor & hash table

Let’s revisit this problem.

In fact, the question asks us to obtain a continuous interval [I,k][I,k][I,k], and find the segmentation point JJJ in this segment, so that the xOR to the left of the segmentation point in the interval is AAA, and the xOR to the right of the segmentation point is BBB. And finally make aaa and BBB equal.

Given that AAA is equal to BBB, it can be deduced that a⊕ B = 0A ⊕ B = 0A ⊕ B =0. Combined with the origin of AAA and BBB, it can be deduced that the xOR of [I,k][I,k][I, K] is 000.

Combined with our preprocessed “prefix Xor” array, we can get:


X o r ( i . k ) = s u m [ k ] The radius s u m [ i – 1 ] = 0 Xor(I, k) = sum[k] ⊕ sum[i-1] = 0

Sum [k]sum[k]sum[k] sum[I −1]sum[I −1]sum[I −1] is equal to sum[I −1]. Therefore, we can use “hash table” to record the subscript set corresponding to each xOR result. Thus, in the case of determining KKK, all eligible iiIs can be found through the complexity of O(1)O(1)O(1).

Note that since our prefix xOR array starts at 111, we need to store a sentinel 000 into the hash table as the boundary. Of course, this step does not require special operations. Simply have KKK execute the loop starting at 000 (using the prefix xor array whose subscript 000 is itself 000).

Code:

class Solution {
    public int countTriplets(int[] arr) {
        int n = arr.length;
        // Preprocess the prefix xor array
        int[] sum = new int[n + 1];
        for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] ^ arr[i - 1];
        int ans = 0;
        {xOR result: [subscript 1, subscript 2...] }
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int k = 0; k <= n; k++) {
            List<Integer> list = map.getOrDefault(sum[k], new ArrayList<>());
            for (int idx : list) {
                int i = idx + 1;
                ans += k - i;
            }
            list.add(k);
            map.put(sum[k], list);
        }
        returnans; }}Copy the code
class Solution {
    public int countTriplets(int[] arr) {
        int n = arr.length;
        // In fact, you can even preprocess the prefix xor array using a variable xor as it traverses
        int xor = 0, ans = 0;
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int k = 0; k <= n; k++) {
            if (k >= 1) xor ^= arr[k - 1];
            List<Integer> list = map.getOrDefault(xor, new ArrayList<>());
            for (int idx : list) {
                int i = idx + 1;
                ans += k - i;
            }
            list.add(k);
            map.put(xor, list);
        }
        returnans; }}Copy the code
  • O(n2)O(n^2)O(n2)
  • Space complexity: O(n)O(n)O(n)

The last

This is the No.1442 of our “Brush through LeetCode” series of articles. The series started on 2021/01/01.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour…

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.