Return to Revisions

You can use a BitSet to improve the time and space complexity of the algorithm. With 1 <= A[i] <= 500, the bit set only need 64 bytes of space. Setting and clearing (or in this case toggling with .flip(bit)) bits are very fast O(1) operations. At the end, the sole remaining bit can be found with .nextSetBit(0).

private static int getAloneNum (int[] arr) {
    BitSet alone = new BitSet(501);

    for (int elem : arr)
        alone.flip(elem);

    return alone.nextSetBit(0);
}

Thinking about streams, it occurred to me a BitSet would also make a good Collector. BitSet::flip works as an accumulator, and BitSet::xor will work as a combiner. This allows the following "one-liner" solution:

import java.util.BitSet;
import java.util.Scanner;

public class Alone {

    public static void main(String[] args) {

        try(Scanner sc = new Scanner(System.in)) {

            int num_tests = sc.nextInt();
            for(int test=0; test < num_tests; test++) {

                int n = sc.nextInt();
                System.out.println(sc.tokens()
                        .limit(n)
                        .mapToInt(Integer::valueOf)
                        .collect(BitSet::new, BitSet::flip, BitSet::xor)
                        .nextSetBit(0));
            }
        }
    }
}

Or, inspired by @PeterTaylor's answer, the BitSet can be skipped entirely, and a simple int used as the accumulator!

                System.out.println(sc.tokens()
                        .limit(n)
                        .mapToInt(Integer::valueOf)
                        .reduce(0, (a,b) -> a ^ b));