Problem: 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. Solution: Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory.
Solution: XORing x with itself gives you 0. Using this property we can find this in linear time.
public int singleNumber(int[] A) { int ans = A[0]; for(int i=1;i<A.length;i++) { ans = ans^A[i]; } return ans; }
Time Complexity: O(N)
Space Complexity: O(1)
This article is contributed by Vishwas Garg. You can also contribute by writing and mail it to us: [email protected]. If you have any better solution then please do comment.
I believe this is assuming that the array of integers has exactly 1 integer that doesn't have any duplicate .. Is that correct?