Return to Revisions

Some code review comments not mentioned by other:

• Unnecessary import:

You have import java.io.IOException; but you are neither catching nor throwing an IOException.

• Possible resource leak

When you open a Closable resource, it is a good habit to .close() it when you are done. This can be automatically done if you use a "try-with-resources" statement:

try (Scanner sc = new Scanner(System.in)) {
   // ... use scanner in here
}
// Scanner is automatically closed here.

Better (or at least other) ways to solve the problem:

You can use a BitSet to improve the time and space complexity of the algorithm. With 1 <= A[i] <= 500, the BitSet only needs 64 bytes of storage. Setting, clearing and (in this case) toggling bits are very fast \$O(1)\$ operations. You don't need to ask whether the element has been encountered before, adding it if it hasn't and removing it if is has; just flipping the corresponding bit performs the add-if-not-present and remove-if-present operations. This has to be done once per input value, resulting in \$O(n)\$. At the end, the sole remaining bit can be found with .nextSetBit(0), which is a \$O(n/64)\$ search operation, yielding an overall \$O(n)\$ algorithm.

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