Given an 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?
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Solution :
Rule of thumb : XORing a number with itself results in 0.
eg: A = [2, 3, 3, 1, 1]
if we XOR the numbers we will be left with the number that only occurred once.
0010 ^ 0011 ^ 0011 ^ 0001 ^ 0001 = 0010 = 2.
Code :
class Solution {public:
int singleNumber(int A[], int n) {
int c = A[0] ;
for(int i=1;i
c=c^A[i];
}
return c;
}
};
Hope that helped!
No comments:
Post a Comment