The following is taken from a job interview:
In a given array, which contains integers, each number repeats itself once except for one, which doesn't repeat. Write a function that finds the number that doesn't repeat.
I thought about using an HashSet, but it might complicate everything...
Any ideas of a simple solution?
You can define an integer "result" initialized to 0, and then you do some bitwise operations by applying a XOR logic to all elements in your array.
At the end, "result" will be equal to the only element that appears only one time.
result = 0
for i in array:
result ^= i
return result
http://en.wikipedia.org/wiki/Bitwise_operation#XOR
For instance, if your array contains the elements [3, 4, 5, 3, 4], the algorithm will return
3 ^ 4 ^ 5 ^ 3 ^ 4
But the XOR operator ^ is associative and commutative, so the result will be also equal to:
(3 ^ 3) ^ (4 ^ 4) ^ 5
Since i ^ i = 0 for any integer i, and i ^ 0 = i, you have
(3 ^ 3) ^ (4 ^ 4) ^ 5 = 0 ^ 0 ^ 5 = 5
I've seen this question before. It's a trick. Assuming all the repeated numbers appear exactly twice you do this:
int result = 0;
for (int a : arr)
result ^= a;
Yet another "ordinary" solution (in Java):
public static int findSingle(int[] array) {
Set<Integer> set = new HashSet<Integer>();
for (int item : array) {
if (!set.remove(item)) {
set.add(item);
}
}
assert set.size() == 1;
return set.iterator().next();
}
In my opinion the solution with XOR is kind of beautiful.
This one is not as fast as XOR but usage of HashSet makes it close to O(n). And it is certainly more readable.
The best answer is already given (XOR-ing the elements), this is to provide an alternative, more general way.
If the input array would be sorted (we can make it sorted), we could simply iterate over the elements in pairs (stepping by 2) and if the elements of the "pair" are different, we're done:
public static int findSingle(int[] arr) {
Arrays.sort(arr);
for (int i = 0, max = arr.length - 1; i < max; i += 2)
if (arr[i] != arr[i + 1])
return arr[i];
return arr[arr.length - 1]; // Single element is the last
}
Note: This solution sorts the input array; if this is unwanted or not allowed, it can be cloned first:
arr = arr.clone();
If input array is sorted, the Arrays.sort(arr) call can be left out of course.
The advantage of this solution is that it can be applied to all types which are comparable and therefore can be sorted (types which implement Comparable), for example String or Date. The XOR solution is limited to numbers only.
Here is a slightly modified version which takes an input array of any element type which is comparable:
public static <E extends Comparable<E>> E findSingle(E[] arr) {
Arrays.sort(arr);
for (int i = 0, max = arr.length - 1; i < max; i += 2)
if (arr[i].compareTo(arr[i + 1]) != 0)
return arr[i];
return arr[arr.length - 1]; // Single element is the last
}
Note: In most cases you could also use arr[i].equals(arr[i + 1]) to compare elements instead of using Comparable.compareTo(). For details read the linked javadoc. Quoting the relevant part:
It is strongly recommended, but not strictly required that
(x.compareTo(y)==0) == (x.equals(y)). Generally speaking, any class that implements theComparableinterface and violates this condition should clearly indicate this fact. The recommended language is "Note: this class has a natural ordering that is inconsistent with equals."
Now you can call this with a String[] for example:
System.out.println(findSingle(new String[] { "1", "2", "3", "1", "3" }));
Output:
2
Final notes:
Starting from the problem statement it is not checked whether there are more than 2 occurrences of the elements, and neither is whether the array length is odd. Also the second example doesn't check for null values, these are to be added if necessary.
Here's a slightly less obfuscated way to do it:
List list = Arrays.asList(a);
int result;
for(int i:a)
{
if(list.indexOf(i)==list.lastIndexOf(i))
{
result = i;
break;
}
}
result will contain the non-repeated value.
