Optymalizacja kodu w zadaniu na czas

Chwil kilka zastanawiam się jak można byłoby jeszcze udoskonalić (w sensie optymalizacyjnym) zadanie ze spoja tj. http://pl.spoj.com/problems/AL_26_04/
Mój kod wygląda następująco i nie przechodzi próby czasu:

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class klasaGlowna {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int iterations = scanner.nextInt();
		
		int[] result = new int[iterations];
		for (int i = 0; i < iterations; i++) {
			int ammountOfNumbers = scanner.nextInt();
			int[] numberInput = new int[ammountOfNumbers];
			for (int j = 0; j < ammountOfNumbers; j++) {
				numberInput[j] = scanner.nextInt();
			}
			
			List<Integer> helpingArray = new ArrayList<>(ammountOfNumbers);
			for (int k = 0; k < ammountOfNumbers; k++) {
				if (helpingArray.indexOf(numberInput[k]) == -1)
					helpingArray.add(numberInput[k]);
				else
					helpingArray.remove(helpingArray.indexOf(numberInput[k]));
			}
			result[i] = helpingArray.get(0);
		}

		for(int e : result){
			System.out.println(e);
		}
	}
} 

Miałby ktoś jakiś pomysł jak usprawnić kod? Może użyć jakiejś innej efektywniejszej struktury?
Czy podział na oddzielne metody wpłynie jakoś na efektywność?

Pamiętam że jak robiłem zadania na SPOJa to scanner z tego co pamiętam działał najwolniej także spróbowałbym najpierw w tą stronę.
Więcej:
http://213.192.104.217/phpBB3-spoj-pl-backup/viewtopic.php?f=10&t=1209

1. java.io.BufferedReader i java.io.PrintWriter są dużo szybsze od scanera i System.out.print,

Moim zdaniem żadna struktura nie jest potrzebna.

    public static void main(String[] args) 
    {
        Scanner scanner = new Scanner(System.in);
        int iterations = scanner.nextInt();
 
        for(int i=0;i<iterations;i++)
        {
            int howMany = scanner.nextInt();
            int result = 0;
            for(int j=0;j<howMany;j++)
            {
                result = result ^ scanner.nextInt();
            }
            System.out.println(result);
        }
    }

@bogdans @eL
Dzięki za próbę pomocy. Przerobiłem mój kod, używając BufferedReader'a i PrintWritera. Oprócz tego, że stał się kompletnie nieczytelny i paskudny dalej nie przechodzi testów. Jak ktoś ma nerwy ze stali to można zajrzeć

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;

public class klasaGlowna {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		int iterations = Integer.parseInt(reader.readLine());
		int[] result = new int[iterations];
		List<Integer> parsedNumbers = new ArrayList<>();
		List<Integer> helpingArray = new ArrayList<>();
		for (int i = 0; i < iterations; i++) {
			int ammountOfNumbers = Integer.parseInt(reader.readLine());
			int[] numberInput = new int[ammountOfNumbers];
			String stringInput = reader.readLine();
			String toParse;
			for (int j = 0; j < ammountOfNumbers; j++) {
				int stringInputLength = stringInput.length();
				while(stringInput.indexOf(" ") != -1){
					int x = stringInput.indexOf(" ");
					toParse = stringInput.substring(0, x);
					int firstParsedFromString = Integer.parseInt(toParse);
					parsedNumbers.add(firstParsedFromString);
					stringInputLength = stringInput.length();
					stringInput = stringInput.substring(x+1,stringInputLength);
				}
				parsedNumbers.add(Integer.parseInt(stringInput));
				for(int cokolwiek = 0;cokolwiek < ammountOfNumbers;cokolwiek++){
					numberInput[cokolwiek] = parsedNumbers.get(cokolwiek);
				}
			}
			for (int k = 0; k < ammountOfNumbers; k++) {
				if (helpingArray.indexOf(numberInput[k]) == -1)
					helpingArray.add(numberInput[k]);
				else
					helpingArray.remove(helpingArray.indexOf(numberInput[k]));
			}
			result[i] = helpingArray.get(0);
			parsedNumbers.clear();
			helpingArray.clear();
		}
		
		PrintWriter out = new PrintWriter(System.out);
		for (int e : result) {
			out.println(e);
			out.flush();
		}
		out.close();
	}
} 

@bogdans jutro spróbuje zamienić twój scanner i out na te zaproponowane przez @eL bo również testu prędkości nie przechodzi. Dzięki za pomysł z użyciem ^

Przy wykorzystaniu ^ i zmianie wejścia na BufferedReader dalej nie przechodzi testu na czas ;/ Jeszcze jakieś pomysły?

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class klasaGlowna {
	public static void main(String[] args) throws NumberFormatException, IOException 
    {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int iterations = Integer.parseInt(reader.readLine());
        int result;
        String toParse;
        for(int i=0;i<iterations;i++)
        {
            int howMany = Integer.parseInt(reader.readLine());
            List<Integer> parsedNumbers = new ArrayList<>();
            String stringInput = reader.readLine();
            int stringInputLength = stringInput.length();
            
            result = 0;
			while(stringInput.indexOf(" ") != -1){
				int x = stringInput.indexOf(" ");
				toParse = stringInput.substring(0, x);
				int firstParsedFromString = Integer.parseInt(toParse);
				parsedNumbers.add(firstParsedFromString);
				stringInputLength = stringInput.length();
				stringInput = stringInput.substring(x+1,stringInputLength);
			}
			parsedNumbers.add(Integer.parseInt(stringInput));
            for(int j=0;j<howMany;j++)
            {
                result = result ^ parsedNumbers.get(j);
            }
            System.out.println(result);
        }
    }
}

Kilka uwag.

1. Nieistotne przyspieszenie można uzyskać wywołując tylko raz System.out.println

            int iterations = ...;
            StringBuilder sb = new StringBuilder();
            //zamiast System.out.println(result);
            sb.append(result + "\n");
            //na końcu
            System.out.println(sb);

2. Masz dwie niepotrzebne operacje: dodanie liczby do kolekcji i pobranie liczby z kolekcji. W pętli while powinno być

    result = result ^ firstParsedFromString;

3. Na moje wyczucie taki sposób czytania jest wolniejszy od Scannera. Najpierw wczytujesz do pamięci wiersz, który może zawierać milion liczb, a potem go wielokrotnie kopiujesz. Każde wywołanie substring, to skopiowanie (trochę krótszego) wiersza w nowe miejsce. Spróbuję porównać czasy czytania dla obu metod - czytał będę z pliku.

Panowie, z ciekawości zrobiłem mały test :)
Czasy są tylko do porównania między sobą - na wejściu dałem mu losowo wygenerowany plik (wg. zasad zadania). U mnie wyszło, że jednak Scanner w tym przypadku wypada słabiutko. Dla porównania także wersja z użyciem HashMap zamiast optymalnego rozwiązania z XOR - nie jest aż tak źle jak mogło by się wydawać. Oczywiście pamięci zje więcej.

Test 1: 1645 ms

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int rounds = Integer.parseInt(br.readLine());
for (int round = 0; round < rounds; round++) {
    int elementsCount = Integer.parseInt(br.readLine());
    int result = Arrays.stream(br.readLine().split(" ")).map(s - > Integer.parseInt(s)).reduce(0, (a, b) - > a ^ b);
    System.out.println(result);
}

Test 2: 1331 ms

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int rounds = Integer.parseInt(br.readLine());
for (int round = 0; round < rounds; round++) {
    int elementsCount = Integer.parseInt(br.readLine());
    int result = 0;
    String[] elements = br.readLine().split(" ");
    for (String element: elements) {
        int el = Integer.parseInt(element);
        result = result ^ el;
    }
    System.out.println(result);
}

Test 3: 16298 ms

Scanner scanner = new Scanner(System.in);
int rounds = scanner.nextInt();
for (int round = 0; round < rounds; round++) {
    int elementsCount = scanner.nextInt();
    int result = 0;
    for (int i = 0; i < elementsCount; i++) {
        result = result ^ scanner.nextInt();
    }
    System.out.println(result);
}

Test 4: 2462 ms

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Map < Integer, Integer > pairs = new HashMap < > ();
int rounds = Integer.parseInt(br.readLine());
for (int round = 0; round < rounds; round++) {
    int elementsCount = Integer.parseInt(br.readLine());
    int result = 0;
    String[] elements = br.readLine().split(" ");
    for (String element: elements) {
        int el = Integer.parseInt(element);
        Integer found = pairs.get(el);
        if (found != null) {
            pairs.remove(el);
        } else {
            pairs.put(el, el);
        }
    }
    pairs.keySet().stream().forEach((last) - > System.out.println(last));
    pairs.clear();
}

SPOJ zaakceptował takie rozwiązanie:

            BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        
            int iterations = Integer.parseInt(reader.readLine());
            StringBuilder sb = new StringBuilder();
            for(int i=0;i<iterations;i++)
            {
                int howMany = Integer.parseInt(reader.readLine());
                int result = 0;
                String[] items = reader.readLine().split(" ");
                for(String item: items)
                {
                    result = result ^ Integer.parseInt(item);
                }
                sb.append(result + "\n");
            }
            System.out.println(sb);