0% completed
Introduction to Bitwise XOR Pattern
Every number in an array appears twice, except one number that appears once. Find the single number.
[1, 4, 2, 1, 3, 2, 3] answer = 4
A hash map can count every value in O(N) time and O(N) space.
Sorting also works, but it takes O(N log N) time.
The XOR operator can solve this problem with one pass and constant extra space.
XOR is written as ^ in many languages. It compares two integers one bit at a time.
Three properties are important:
a ^ a = 0: equal values cancel.a ^ 0 = a: zero does not change a value.- XOR operations can be applied in any order.
.....
.....
.....
Miguel
· 2 years ago
I think that it would be helpful to mention that XOR is involute, meaning that it is a self-inverse function. This means that we can apply xor some number of times and undo the operations by applying the XOR function again.
This is why we can effectively "XOR in" all 1->n numbers into x1 and then "XOR in" all numbers in our actual list into x2. Then when we XOR x1 by x2, we are effectively undoing all the numbers we "XOR'ed into" x2 from x1, leaving us only with the number that was never "XOR'ed into" x1 (our missing number).
ex: 0 ^ 1 = 1 ^ 2 = 3 ^ 1 = 2 ^ 2 = 0 (note that reapplying xor got us back to 0)
ex: 0 ^ 1 = 1 ^ 2 = 3 ^ 3 = 0 ^ 4 = 4 ^ 3 = 7 ^ 2 = 5 ^ 1 = 4 (note, we are left with the only number we did not XOR in twice)
sweetykumari
· 3 years ago
I didn't understand both for loop:
//why we are xor nums.Length+1?
//why we are xor nums.Length+1?
int x1 = 1; for (int i = 2; i <= n; i++) x1 = x1 ^ i;
////why we are xor nums.Length; isnt it should be nums.Length-1? // x2 represents XOR of all values in arr int x2 = arr[0]; for (int i = 1; i < n-1; i++) x2 = x2 ^ arr[i];
Sonia
· 4 years ago
this gives wrong answer for missing number question on leetcode
Yogi Paturu
· 5 years ago
Are the C++ and JS solutions supposed to be swapped for the first algorithm?
Reading Progress
0%