Ingenious use of xor properties to achieve the optimal solution | Java brush title punch card

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

Topic describes

This is 1734 on LeetCode. Decoding xOR permutations with medium difficulty.

Tag: math, xor

You are given an integer array perm, which is the array of the first n positive integers, and n is odd.

It is encrypted to another integer array encoded of length n-1, satisfying encoded[I] = perm[I] XOR perm[I + 1]. For example, if perm = [1,3,2], then encoded = [2,1].

Given your encoded array, return the original array perm. They guarantee that the answer exists and is unique.

Example 1:

Explanation: if perm = [1,2,3], then encoded = [1 XOR 2,2 XOR 3] = [3,1]Copy the code

Example 2:

Input: encoded = [6,5,4,6]Copy the code

Tip:

• 3 <= n < 
  $10^5$
• N is odd.
• encoded.length == n – 1

---

Fundamental analysis

We know that xOR operations have the following properties:

1. If the same value is xor, the result is 000
2. Xor of any value with 000 results in the value itself
3. Xor itself satisfies the commutative law

The main difference between this case and the xOR array decoded in 1720 is that the first element is not given.

Therefore, finding the “first element” or “last element” of the array of answers can serve as a question entry point.

---

Mathematics & Simulation

We define the answer array as ans[], which has a length of n, and n is odd.

That is [ans [0], ans [1], ans [2],…, ans [n – 1]] [ans [0], ans [1], ans [2],…, ans [n – 1]] [ans [0], ans [1], ans [2],…, ans [n – 1]].

Given an array of encoded [] is [ans [0] radius ans [1], ans [1] the radius ans [2],…, ans [n – 3] the radius ans [n – 2), ans [n – 2) radius ans [n – 1]] [ans [0] radius ans [1], Ans [1] ⊕ ANS [2],… Ans [n – 2) radius ans [n – 1]] [ans [0] radius ans [1], ans [1] the radius ans [2],…, ans [n – 3] radius ans [n – 2), ans [n – 2) radius ans [n – 1]], the length of n – 1.

Since the same array member ANS [x] appears every adjacent bit, consider xOR “every other bit” :

1. fromencoded[]The first
   $0$Bit start, every other bit xor: available
   $Ans [0] ⊕ ANS [1] ⊕… The radius ans [n – 2)$That in addition toans[]In the array
   $ans[n – 1]$Other than all xOR results.

2. usingans[]An array isnA permutation of positive integers, we get
   $Ans [0] ⊕ ANS [1] ⊕… ⊕ ⊕ ANS [n-2] ⊕ ANS [n-1]$, i.e.,ans[]Xor results of all elements in an array.

If the two expressions are xor, ans[n−1]ans[n-1]ans[n−1] is obtained.

With the ending element, the problem becomes a simulation similar to the 1720. Decoded xOR array.

Code:

class Solution {
    public int[] decode(int[] encoded) {
        int n = encoded.length + 1;
        int[] ans = new int[n];
        // find all xor except for ans[n-1]
        int a = 0;
        for (int i = 0; i < n - 1; i += 2) a ^= encoded[i];
        // Find all xor of ans
        int b = 0;
        for (int i = 1; i <= n; i++) b ^= i;
        // Get ans[n-1] from the back
        ans[n - 1] = a ^ b;
        for (int i = n - 2; i >= 0; i--) {
            ans[i] = encoded[i] ^ ans[i + 1];
        }
        returnans; }}Copy the code

• Time complexity: O(n)O(n)O(n)
• Spatial complexity: Build the same order of magnitude array of answers. The complexity is O(n)O(n)O(n)

---

The last

This is the No.1734 of our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 topics in LeetCode by the start date, some of which have locks.

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.