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

Topic describes

This is the array xor operation on LeetCode 1486. The difficulty is simple.

Tag: “math”, “simulation”

I give you two integers, n and start.

The array nums is defined as: nums[I] = start + 2* I (subscripts start from 0) and n == nums.length.

Return the result of bitwise XOR (XOR) of all elements in NUMS.

Example 1:

Input: n = 5, start = 0 Output: 8 Explanation: array nums is [0, 2, 4, 6, 8], where (0 ^ 2 ^ 4 ^ 6 ^ 8) = 8 "^" is the bitwise XOR operator.Copy the code

Example 2:

Input: n = 4, start = 3 Output: 8 Description: array nums is [3, 5, 7, 9] where (3 ^ 5 ^ 7 ^ 9) = 8.Copy the code

Example 3:

Input: n = 1, start = 7 Output: 7Copy the code

Example 4:

Input: n = 10, start = 5 Output: 2Copy the code

Tip:

  • 1 <= n <= 1000
  • 0 <= start <= 1000
  • n == nums.length

simulation

Data range is only 10310^3103, according to the question requirements from the beginning of the simulation can be.

Code:

class Solution {
    public int xorOperation(int n, int start) {
        int ans = start;
        for (int i = 1; i < n; i++) {
            int x = start + 2 * i;
            ans ^= x;
        }
        returnans; }}Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(1)O(1)O(1)

mathematics

The data range of the above method is 10810^8108 with high probability that TLE will occur.

If the data range was 10810^8108, the difficulty would be classified as “medium” or “difficult”.

In fact, there is a “mathematical law” solution to this problem.

The formula is start⊕(start+2)⊕(start+4)⊕… The radius (start + 2 ∗ (n – 1)) start the radius (+ 2) start the radius (start + 4) radius… The radius (start + 2 * (n – 1)) start the radius (+ 2) start the radius (start + 4) radius… The radius (start + 2 ∗ (n – 1)).

We found that only the value 222 in the original formula was a fixed coefficient (given by the problem), so we considered to propose it.

The new formula IS S ⊕(s+1)⊕(s+2)⊕… ⊕(S +(n−1))∗2s ⊕(S + 1) ⊕(S + 2) ⊕… ⊕(S + (n-1)) * 2s⊕(S +1)⊕(S +2)⊕… ⊕(S +(n−1))∗2, where S =start/2s =start/2s =start/2.

The reason why we do this is because we want to take advantage of the xor property of 1⊕2⊕3=01 ⊕2⊕3=01 ⊕2⊕3=0.

But at this point, we find that the “new expression” is not the same as the “original expression”.

We need to consider the difference between the two:

It’s not hard to see how you can convert the original form into the new collective divide
2 2 The operation will be equivalent to each
i t e m item The “xOR operation” is calculated independently of each other, so the “xOR operation” will not affect the calculation result of the moving part.

In essence, the transformation of “original” into “new” is the final answeransThe “move right” operation is performed. So if YOU want to get backans, we need to move it “left” again to fill in the last xOR result.

The original type results = new < < 1 | e, eee is an exclusive or end (only 000 or 111, the remaining high for 000).

We re-observe the “original formula” and find that each item itemItemItem in the formula has the same parity, which means that its lowest binary value is the same.

The last digit e = n &start &1.

The remaining problem is how to calculate the “new” result without ergodicating, and the purpose of the transformation is to take advantage of the xor property of 1⊕2⊕3=01 ⊕2⊕3=01 ⊕2⊕3=0.

In fact, this formula is of general conclusion: 4 (I) the radius (4 I + 1) the radius (4 I + 2) radius (4 + 3) I = 4 (I) the radius (4 I + 1) the radius (4 I + 2) radius (4 + 3 I) = 4 (I) the radius (4 I + 1) the radius (4 I + 2) radius (4 + 3 I) = 0.

So you only need to discuss the last item %4, which is the “conclusion,” as described in the calC section of the code.

So to summarize, let’s say our final answer is zeroans. The whole process is essentially taking each of these
i t e m item We move it one place to the right
2 2 ),ansThe result of all but the lowest digit; thenansI’m going to shift it one bit to the left
2 2 ) to replace the lost last bit result. To make up is to usen 和 startThe discussion of “parity”.

Code:

class Solution {
    int calc(int x) {
        if (x % 4= =0) return x;
        else if (x % 4= =1) return 1;
        else if (x % 4= =2) return x + 1;
        else return 0;
    }
    public int xorOperation(int n, int start) {
        // Divide the whole thing by 2, using %4 to calculate the result of dividing the "lowest bit" in ANS
        int s = start >> 1;
        int prefix = calc(s - 1) ^ calc(s + n - 1);
        // Calculate the "lowest bit" result in ANS using "parity"
        int last = n & start & 1;
        int ans = prefix << 1 | last;
        returnans; }}Copy the code
  • Time complexity: O(1)O(1)O(1)
  • Space complexity: O(1)O(1)O(1)

The last

This is the No.1486 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.