current position:Home>[algorithm learning] 1486 Array XOR operation (Java / C / C + + / Python / go / trust)

[algorithm learning] 1486 Array XOR operation (Java / C / C + + / Python / go / trust)

2022-01-29 15:54:47 White hat of the second leader

Thank you very much for reading this article ~ welcome 【 give the thumbs-up 】【 Collection 】【 Comment on 】~ It's not hard to give up , But persistence must be cool ~ I hope all of us can make a little progress every day ~ This paper is written by The white hat of the second leader https://juejin.cn/user/2771185768884824/posts Original blog ~


1486. Array XOR operation :

Here are two integers ,n and start .

Array nums Defined as :nums[i] = start + 2 * i( Subscript from 0 Start ) And n == nums.length .

Please return nums All elements in the are bitwise XOR (XOR) Results after .

Examples 1

 Input :
	n = 5, start = 0
 Output :
	8
 explain :
	 Array  nums  by  [0, 2, 4, 6, 8], among  (0 ^ 2 ^ 4 ^ 6 ^ 8) = 8 .
     "^"  For bitwise XOR  XOR  Operator .
 Copy code 

Examples 2

 Input :
	n = 4, start = 3
 Output :
	8
 explain :
	 Array  nums  by  [3, 5, 7, 9], among  (3 ^ 5 ^ 7 ^ 9) = 8.
 Copy code 

Examples 3

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

Examples 4

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

Tips

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

analysis

We can directly follow the meaning of the question , Cycle of violence , So time complexity is O(n), Is there a time complexity of O(1) The algorithm of ?

remember x As a variable ,^ Is an XOR operation , Then the XOR operation satisfies the following properties :

  1. x ^ x = 0;
  2. x ^ 0 = x;
  3. x ^ y = y ^ x( Commutative law );
  4. (x ^ y) ^ z = x ^ (y ^ z)( Associative law );
  5. x ^ y ^ y = x( reflexivity );
  6. If x yes 4 Multiple ,x ^ (x + 1) ^ (x + 2) ^ (x + 3) = 0;
  • The problem is to calculate Result formula by :start ^ (start + 2) ^ (start + 4) ^ ⋯ ^(start + 2 * (n − 1)).
  • If there's a function sumXor(x) You can calculate 0 ^ 1 ^ 2 ^ ⋯ ^ x .
  • For a variable x and n, Calculation sumXor(s - 1) ^ sumXor(s + n - 1) Result , According to the above nature 1 Can be 0 ^ 1 ^ 2 ^ ... ^ (s - 1) The value of offset is 0, It becomes 0 ^ s ^ (s + 1) ^ (s + 2) ^ ⋯ ^ (s + n - 1) , according to nature 2 Knowable and 0 Do XOR or do it yourself , The end result is s ^ (s + 1) ^ (s + 2) ^ ⋯ ^ (s + n - 1) , This result is very close to what we want to calculate .
  • If we make s = start / 2 , hold Result formula convert to (s ^ (s + 1) ^ (s + 2) ^ ⋯ ^ (s + n - 1)) * 2, This does not hold , Because I'm doing it 2 Operation of , The lowest bit is lost , But we can deal with the lowest bit alone .
  • Observe Result formula You know (start + 2),(start + 4) ,... ,(start + 2 * (n − 1)) The parity properties of are the same , And and start Agreement , That is, the lowest position is either 0, Or both. 1, Only one 1 It's only when you do XOR 1. It's just start Is odd and n When it's an odd number , The lowest point of the final result e It's just 1.
  • At this time Result formula Can be converted to : ((sumXor(s - 1) ^ sumXor(s + n - 1)) * 2) | e .

As long as we can implement the function sumXor(x), Then the problem calculation can do O(1) Time complexity of , according to nature 6 and nature 2 We just need to think about it x Divide 4 The remainder of , That is, the lowest 2 position , The following derivation can be obtained :

x % 4 = 0 Binary bit of :xx...x00 x % 4 = 1 Binary bit of :xx...x01 x % 4 = 2 Binary bit of :xx...x10 x % 4 = 3 Binary bit of :xx...x11

  • x % 4 = 0,sumXor(x) = x;
  • x % 4 = 1,sumXor(x) = (x - 1) ^ x, Simplify and get sumXor(x) = 1;
  • x % 4 = 2,sumXor(x) = (x - 2) ^ (x - 1) ^ x, Simplify and get sumXor(x) = x | 1;
  • x % 4 = 3,sumXor(x) = 0;
  • x % 4 Equate to x & 3 The operation of , And in theory & Operation is better than % Faster operation ;

Answer key

java

class Solution {
    public int xorOperation(int n, int start) {
        int s = start >> 1, e = n & start & 1;
        int ret = sumXor(s - 1) ^ sumXor(s + n - 1);
        return ret << 1 | e;
    }

    public int sumXor(int x) {
        switch (x & 3) {
            case 0:
                return x;
            case 1:
                return 1;
            case 2:
                return x | 1;
            default:
                // x & 3 == 3
                return 0;
        }
    }
}
 Copy code 

c

int xorOperation(int n, int start) {
    int s = start >> 1, e = n & start & 1;
    int ret = sumXor(s - 1) ^ sumXor(s + n - 1);
    return ret << 1 | e;
}

int sumXor(int x) {
    switch (x & 3) {
        case 0:
            return x;
        case 1:
            return 1;
        case 2:
            return x | 1;
        default:
            // x & 3 == 3
            return 0;
    }
}
 Copy code 

c++

class Solution {
public:
    int xorOperation(int n, int start) {
        int s = start >> 1, e = n & start & 1;
        int ret = sumXor(s - 1) ^ sumXor(s + n - 1);
        return ret << 1 | e;
    }

    int sumXor(int x) {
        switch (x & 3) {
            case 0:
                return x;
            case 1:
                return 1;
            case 2:
                return x | 1;
            default:
                // x & 3 == 3
                return 0;
        }
    }
};
 Copy code 

python

class Solution:
    def xorOperation(self, n: int, start: int) -> int:
        def sumXor(x):
            if x % 4 == 0:
                return x
            if x % 4 == 1:
                return 1
            if x % 4 == 2:
                return x | 1
            return 0
        s = start >> 1
        e = n & start & 1
        ans = sumXor(s - 1) ^ sumXor(s + n - 1)
        return ans << 1 | e
 Copy code 

go

func xorOperation(n, start int) (ans int) {
    s, e := start>>1, n&start&1
    ret := sumXor(s-1) ^ sumXor(s+n-1)
    return ret<<1 | e
}

func sumXor(x int) int {
    switch x & 3 {
        case 0:
            return x
        case 1:
            return 1
        case 2:
            return x | 1
        default:
            return 0
    }
}
 Copy code 

rust

impl Solution { 
  pub fn xor_operation(n: i32, start: i32) -> i32 {
    let s = start >> 1;
    let e = n & start & 1;
    let ret = Solution::sum_xor(s - 1) ^ Solution::sum_xor(s + n - 1);
    return ret << 1 | e
  }

  fn sum_xor(x: i32) -> i32 {
    match x & 3 {
      0 => x,
      1 => 1,
      2 => x | 1,
      _ => 0
    }
  }
}
 Copy code 

 Insert picture description here


Original title transmission gate


copyright notice
author[White hat of the second leader],Please bring the original link to reprint, thank you.
https://en.pythonmana.com/2022/01/202201291554466782.html

Random recommended