Problem
There are N+2 different integers in an array. N integers appeared even number of times, 2 integers appeared odd number of times. Please find these 2 numbers with space cost O(1).
For example, given array
{1, 2, 1, 2, 1, 4, 6, 3, 3, 4}
the output should be 1 and 6.
{1, 2, 1, 2, 1, 4, 6, 3, 3, 4}
the output should be 1 and 6.
Solution
The normal solution is to use a hashMap to store the frequency of the the integers.
With the constraint of space cost O(1), we need to use math to solve it, which won't always be apparent.
xor operation has the following properties:
a^a = 0
0^a = a
so if we apply xor to all the numbers in the array, we end up get the 2 numbers' xor
a^b = c
in order to get a or b from c, we need to cancel out a or b with xor. what's the difference of a and b? Assuming c's binary is 100001, we then know, a should look like 1xxxx1 and b should look like x0xxxx0 (or a looks like x0xxxx0 and b looks like 1xxxx1, a and b are in interchangeable positions), so that their xor generate 1xxxx1. Assuming c looks like 100100, we will know, a looks like 1xx1xx and b looks like x0xx0xx so that their xor can be 1xx1xx. That means, a and b is not symmetric at those 1 positions. We can use this symmetry break to get rid of one of them.
How to get rid of one of them? The way is to find all the numbers in the array looks like ...xxxx1xx, that will include a and some numbers that appear even number of times, but it won't include b, because b looks like ...xxxx0xx. If We make an xor for this list, we got a or b.
Finally we got b = c^a.
class OddFinder{
public static void findOddAppearance(int[] a) {
int c = 0;
for(int i = 0; i < a.length; i++) {
c ^= a[i];
}
int pos = 0;
int tmpC = c;
while((tmpC&1) != 1) {
tmpC = tmpC>>1;
pos++;
}
int x = 0;
for(int i = 0; i < a.length; i++) {
int t = a[i];
for(int j = 0; j < pos; j++) {
t = t >> 1;
}
if((t&1)==1)
x = x^t;
}
System.out.println("x=" + x);
System.out.println("y=" + (x^c));
}
public static void main(String...args) {
int[] a = new int[]{1, 2, 1, 2, 1, 4, 6, 3, 3, 4};
findOddAppearance(a);
}
}
public static void findOddAppearance(int[] a) {
int c = 0;
for(int i = 0; i < a.length; i++) {
c ^= a[i];
}
int pos = 0;
int tmpC = c;
while((tmpC&1) != 1) {
tmpC = tmpC>>1;
pos++;
}
int x = 0;
for(int i = 0; i < a.length; i++) {
int t = a[i];
for(int j = 0; j < pos; j++) {
t = t >> 1;
}
if((t&1)==1)
x = x^t;
}
System.out.println("x=" + x);
System.out.println("y=" + (x^c));
}
public static void main(String...args) {
int[] a = new int[]{1, 2, 1, 2, 1, 4, 6, 3, 3, 4};
findOddAppearance(a);
}
}
The time cost is O(N) and the space cost is O(1)
