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

algorithm learning array xor operation

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://le-yi.blog.csdn.net/ 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 .

Examples 2

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

Examples 3

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

Examples 4

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

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;
}
}
}

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;
}
}

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;
}
}
};

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

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
}
}

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
}
}
}

 Insert picture description here


Original title transmission gate


版权声明
本文为[The white hat of the second leader]所创,转载请带上原文链接,感谢
https://pythonmana.com/2021/10/20211014012901075a.html

  1. Python題,我剛學,還不會
  2. Je viens d'apprendre, pas encore.
  3. 云计算开发:Python3-find()方法详解
  4. Real time access to stock data, free—— Python crawler Sina stock actual combat
  5. Développement de l'informatique en nuage: détails de la méthode Python 3 - find ()
  6. 如何使用Python进行超参调参和调优
  7. 如何使用Python進行超參調參和調優
  8. Comment utiliser Python pour le réglage hyperparamétrique
  9. Première connaissance du module urllib Python
  10. Python入门:看了这篇文章如果1个小时没法入门Python,那么还是换个语言吧!!
  11. Python(day1):Python 3 教程
  12. Python(day3):Python3 安装与环境搭建
  13. Python (day3): installation et environnement Python 3
  14. Python (day1): tutoriel Python 3
  15. Démarrer avec Python: Si vous ne pouvez pas commencer avec Python en une heure, changez de langue!!
  16. Pandas:DataFrame对象的基础操作
  17. 关于#python#的问题:月球上物体的体重在地球上的16.5%,编写程序输出未来10年在地球上和月球上的体重状况
  18. 反转一个3位整数(Python 实现)
  19. Inverse un entier de 3 bits (implémentation Python)
  20. Questions sur # Python #: les objets lunaires pèsent 16,5% de la masse de la terre et un programme est programmé pour produire la masse de la terre et de la lune au cours des 10 prochaines années
  21. Compared with Excel, it is easy to learn Python report automation practice!
  22. 7 excellent open source libraries for learning Python Programming
  23. Use of Python pandas!!!!! Explain in detail
  24. Python Qt GUI设计:QPrinter打印图片类(基础篇—21)
  25. Use of Python pandas!!!!! Explain in detail
  26. 2n行输入,Python,判断字母个数
  27. Notes de Python (XV): dérivation de liste
  28. Notes sur Python (XVI): générateur et Itérateur
  29. Notes de Python (18): décorateur
  30. 2n entrée de ligne, Python, nombre de lettres de jugement
  31. Notes Python (17): fermetures
  32. Notes sur Python (20): fonctions d'ordre supérieur intégrées
  33. 想问问这个Python编程咋做呀?
  34. 想問問這個Python編程咋做呀?
  35. Vous voulez savoir ce que fait cette programmation python?
  36. 11.5K Star,一个开源的 Python 静态类型检查库
  37. Sweetviz:让你只需三行代码实现Python探索性数据分析
  38. Sweetviz:讓你只需三行代碼實現Python探索性數據分析
  39. Sweetviz: vous permet d'effectuer une analyse exploratoire des données python avec seulement trois lignes de code
  40. 11.5k Star, une bibliothèque de vérification de type statique Python Open Source
  41. 刚学Python,想让大大给我解释一下代码
  42. 剛學Python,想讓大大給我解釋一下代碼
  43. Je viens d'apprendre Python et je veux que tu m'expliques le Code.
  44. Python QT GUI Design: qmainwindow, QWidget and qdialog window classes (Fundamentals - 10)
  45. Python爬虫项目实战:快手网页版滑块captchaSession分析
  46. python计算时间十二小时制
  47. Temps de calcul Python 12 heures
  48. Python crawler Project actual Fighting: faster Web Version Slider CAPTCHA session Analysis
  49. Python要学习多久可以掌握?多久可以精通?
  50. Combien de temps Python va - t - il apprendre à maîtriser? Combien de temps faut - il pour maîtriser?
  51. 从官网上下载的python安装包安装不了
  52. 深度学习项目:如何使用Python和OpenCV进行人脸识别
  53. python编辑语言如内容所示
  54. La langue d'édition Python est affichée dans le contenu
  55. 有谁知道这怎么回事嘛(Python的简单代码)
  56. 有誰知道這怎麼回事嘛(Python的簡單代碼)
  57. Qui sait ce qui se passe?
  58. Python求某个数的因数【因数是指能被这个数整除的数。例如6的因数有:1、2、3、6; 7的因数有:1、7; 8的因数有:1、2、4、8】。
  59. Python calcule les facteurs d'un nombre [les facteurs sont des nombres qui peuvent être divisés par ce nombre. Par exemple, les facteurs de 6 sont: 1, 2, 3, 6; les facteurs de 7 sont: 1, 7; et les facteurs de 8 sont: 1, 2, 4, 8].
  60. 如何创建一个python程序来模拟电影院的座位预订