Find a Number that Appears Only once in array of Duplicates

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.

One Thought on “Find a Number that Appears Only once in array of Duplicates

  1. I believe this is assuming that the array of integers has exactly 1 integer that doesn't have any duplicate .. Is that correct?

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation