Annettuna on lista lukuja, jossa jokainen luku esiintyy kahdesti paitsi yksi luku esiintyy vain kerran. Tehtäväsi on etsiä tämä pariton luku.

Listan jokainen alkio on kokonaisluku välillä $1 \dots 10^9$ ja listassa on enintään $10^5$ alkiota. Tavoitteena on, että algoritmin aikavaativuus on $O(n \log n)$.

Python

Toteuta tiedostoon findodd.py funktio find, joka ilmoittaa parittoman luvun.

def find(t):
    # TODO

if __name__ == "__main__":
    print(find([2,2,4,3,4])) # 3
    print(find([1,2,3,4,1,2,3])) # 4
    print(find([1])) # 1
    print(find([1,4,2,3,2,3,4])) # 1
    print(find([4,1,3,2,3,2,1])) # 4

Java

Toteuta tiedostoon FindOdd.java metodi find, joka ilmoittaa parittoman luvun.

public class FindOdd {
    public int find(int[] t) {
        // TODO
    }

    public static void main(String[] args) {
        FindOdd f = new FindOdd();
        System.out.println(f.find(new int[] {2,2,4,3,4})); // 3
        System.out.println(f.find(new int[] {1,2,3,4,1,2,3})); // 4
        System.out.println(f.find(new int[] {1})); // 1
        System.out.println(f.find(new int[] {1,4,2,3,2,3,4})); // 1
        System.out.println(f.find(new int[] {4,1,3,2,3,2,1})); // 4
    }
}