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】
- Little knowledge , Great challenge ! This article is participating in “ A programmer must have a little knowledge ” Creative activities .
- This article also participates in 「 Digging force Star Program 」 , Win a creative gift bag , Challenge creation incentive fund .
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 :
- x ^ x = 0;
- x ^ 0 = x;
- x ^ y = y ^ x( Commutative law );
- (x ^ y) ^ z = x ^ (y ^ z)( Associative law );
- x ^ y ^ y = x( reflexivity );
- 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
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
The sidebar is recommended
- [Python introduction project] use Python to generate QR code
- Quickly build Django blog based on function calculation
- Python collects and monitors system data -- psutil
- Python interface test unittest usage details
- Implementation of top-level design pattern in Python
- You can easily get started with Excel. Python data analysis package pandas (VII): breakdown
- Python simulation random coin toss (non optimized version)
- Using linear systems in python with scipy.linalg
- Using linear systems in python with scipy.linalg
- Together with Python to do a license plate automatic recognition system, fun and practical!
guess what you like
-
Using linear systems in python with scipy.linalg
-
Fast power modulus Python implementation of large numbers
-
Quickly build Django blog based on function calculation
-
This paper clarifies the chaotic switching operation and elegant derivation of Python
-
You can easily get started with Excel pandas (I): filtering function
-
You can easily get started with Excel. Python data analysis package pandas (II): advanced filtering (I)
-
You can easily get started with Excel. Python data analysis package pandas (2): advanced filtering (2)
-
How does Python correctly call jar package encryption to get the encrypted value?
-
Python 3 interview question: give an array. If there is 0 in the array, add a 0 after 0, and the overall array length remains the same
-
Python simple Snake game (single player mode)
Random recommended
- Using linear systems in python with scipy.linalg
- Python executes functions and even code through strings! Come and understand the operation of such a top!
- Decoding the verification code of Taobao slider with Python + selenium, the road of information security
- [Python introduction project] use Python to generate QR code
- Vanessa basks in her photos and gets caught up in the golden python. There are highlights in the accompanying text. She can't forget Kobe after all
- [windows] Python installation pyteseract
- [introduction to Python project] create bar chart animation in Python
- Python series tutorials 116
- Python code reading (chapter 35): fully (deeply) expand nested lists
- Practical series 1 ️⃣ Wechat applet automatic testing practice (with Python source code)
- Python Basics: do you know how to use lists?
- Solution of no Python 3.9 installation was detected when uninstalling Python
- [Python homework] coupling network information dissemination
- [common links of Python & Python]
- [Python development tool tkinterdiesigner]: example: develop stock monitoring alarm using Tkinter desinger
- [Python development tool Tkinter designer]: Lecture 1: introduction to the basic functions of Tkinter Designer
- [introduction to Python tutorial] use Python 3 to teach you how to extract any HTML main content
- Python socket implements UDP server and client
- Python socket implements TCP server and client
- leetcode 1974. Minimum Time to Type Word Using Special Typewriter(python)
- The mobile phone uses Python to operate picture files
- [learning notes] Python exception handling try except...
- Two methods of using pandas to read poorly structured excel. You're welcome to take them away
- Python sum (): the summation method of Python
- Practical experience sharing: use pyo3 to build your Python module
- Using Python to realize multitasking process