Return to Answer

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

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.

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

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

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

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