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):

1
2
3
4
5
6
7

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):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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}));
 	}
}