The challenge
Given an array of integers, find the one that appears an odd number of times.
There will always be only one integer that appears an odd number of times.
The solution in Java code
Option 1 (using streams):
import static java.util.Arrays.stream;
public class FindOdd {
public static int findIt(int[] arr) {
return stream(arr).reduce(0, (x, y) -> x ^ y);
}
}
Option 2 (using xor):
public class FindOdd {
public static int findIt(int[] A) {
int odd = 0;
for (int i : A) {
odd ^= i;
}
return odd;
}
}
Option 3 (using a TreeSet):
import java.util.TreeSet;
public class FindOdd {
public static int findIt(int[] A) {
final TreeSet<Integer> set = new TreeSet<>();
for (int x : A) {
if (set.contains(x)) {
set.remove(x);
} else {
set.add(x);
}
}
return set.first();
}
}
Test cases to validate our solution
import org.junit.Test;
import static org.junit.Assert.assertEquals;
public class FindOddTest {
@Test
public void findTest() {
assertEquals(5, FindOdd.findIt(new int[]{20,1,-1,2,-2,3,3,5,5,1,2,4,20,4,-1,-2,5}));
assertEquals(-1, FindOdd.findIt(new int[]{1,1,2,-2,5,2,4,4,-1,-2,5}));
assertEquals(5, FindOdd.findIt(new int[]{20,1,1,2,2,3,3,5,5,4,20,4,5}));
assertEquals(10, FindOdd.findIt(new int[]{10}));
assertEquals(10, FindOdd.findIt(new int[]{1,1,1,1,1,1,10,1,1,1,1}));
assertEquals(1, FindOdd.findIt(new int[]{5,4,3,2,1,5,4,3,2,10,10}));
}
}
