LeetCode 136 - Single Number

https://leetcode.com/tag/bit-manipulation/

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

Input: [2,2,1]
Output: 1

Example 2:

Input: [4,1,2,1,2]
Output: 4

https://leetcode.com/problems/single-number/discuss/42997/My-O(n)-solution-using-XOR

known that A XOR A = 0 and the XOR operator is commutative, the solution will be very straightforward.
`

int singleNumber(int A[], int n) {
    int result = 0;
    for (int i = 0; i<n; i++)
    {
  result ^=A[i];
    }
 return result;
}

https://leetcode.com/problems/single-number/discuss/43201/Easy-Java-solution-(tell-you-why-using-bitwise-XOR)

we use bitwise XOR to solve this problem :

first , we have to know the bitwise XOR in java

1. 0 ^ N = N
2. N ^ N = 0

So..... if N is the single number

N1 ^ N1 ^ N2 ^ N2 ^..............^ Nx ^ Nx ^ N

= (N1^N1) ^ (N2^N2) ^..............^ (Nx^Nx) ^ N

= 0 ^ 0 ^ ..........^ 0 ^ N

= N