The Odd Number

View as PDF

Submit solution

Points: 7
Time limit: 0.5s
Memory limit: 4M

Author:
Problem type

Cindy has challenged Weiwei a simple question today, and Weiwei promises to give the answer before lunch break, or else he is going to buy lunch for Cindy. There are only 5 minutes left until lunch starts, but Weiwei still has no idea whatsoever about how to solve this problem. You, as Weiwei's best friend, are trying to help him find out the answer.

Weiwei is given a multiset of N integers. Out of all N integers, only one appeared an odd number of times, and all others have appeared an even number of times. What is the value of this integer?

Input Specification

The first line of input contains the integer N (1 \le N \le 10^6).

Next N lines: one integer x (-10^9 \le x \le 10^9), which is a number in the multiset.

Output Specification

Output one integer, the integer that occurred an odd number times.

Sample Input

5
3
3
18
4
4

Sample Output

18

Comments


  • 1
    ScriptKitty  commented on July 17, 2018, 5:54 a.m.

    How come I get a memory error from actually submitting nothing? Submitting 1 uses up 5.67 MB.

    I'm not sure what I'm doing wrong


    • 4
      injust  commented on July 17, 2018, 6:32 a.m.

      The problem isn't solvable in all languages, because of the low global memory limit. In particular, PyPy consumes a lot of memory.


  • 4
    m4m3sh1b4  commented on June 26, 2018, 2:01 p.m.

    Hint: If you keep getting TLE's in Java, try BufferedReader --> https://dmoj.ca/tips/

    You might not need it but it will make your life much easier! :D


  • 0
    rsylshzxdkh  commented on Aug. 16, 2017, 2:56 p.m.

    Java outofmemory error?


    • 3
      Kirito  commented on Aug. 16, 2017, 5:09 p.m.

      Your solution requires storing all N integers, which takes \mathcal O(N) memory. Try to aim for sublinear memory.


  • -1
    Daniel_Weintraub  commented on Dec. 24, 2015, 9:34 p.m.

    Just wondering if this question is possible in Python?


    • 0
      Xyene  commented on Dec. 24, 2015, 9:35 p.m.

      Yes, this problem is doable in any language (it is not computationally intensive).


      • 0
        aeternalis1  commented on July 17, 2017, 10:54 p.m.

        I managed to find a method to fit my submission under the time limit, but it ends up exceeding the memory limit. If I import sys and read all the input data with sys.stdin.read().split('\n'), I get up to 100 M of memory. However, if I use any other method to read input it simply takes too long. There still has yet to be a precedent of a python solution to this problem.


      • -6
        Daniel_Weintraub  commented on Dec. 24, 2015, 9:50 p.m.

        This comment is hidden due to too much negative feedback. Click here to view it.


  • 2
    kobortor  commented on Sept. 20, 2015, 12:06 a.m.

    Why did arock's solution pass using 26 MB? The problem description says its limited to only 4 MB.


    • 3
      Xyene  commented on Sept. 20, 2015, 10:08 a.m. edit 3

      For Java, MLE is calculated based off the size of the Java heap. As such, it does not take the overhead of the JVM into account, though the number displayed for submission statuses is the memory the entire JVM took. arock's submission allocated under 4MB of heap space, though the overall JVM usage was much higher. See this and this for more info.


  • 4
    bobhob314  commented on Sept. 19, 2015, 7:11 p.m.

    Heya, got nothing but love for you guys; just pointing out a point inconsistency with Utrka (6 pts.)


    • 3
      moladan123  commented on Dec. 29, 2015, 10:16 p.m.

      That question is actually a fair bit easier than this one. The solution I used on that one gives me both TLE and MLE on this one.


      • -7
        NT_AUTHORITY_SYSTEM  commented on Aug. 8, 2017, 10:00 p.m.

        This comment is hidden due to too much negative feedback. Click here to view it.


  • 7
    bruce  commented on Sept. 19, 2015, 1:43 p.m.

    If you submit your solution in C++ or C++11, you may get IR errors. Try to solve it in C.


  • 11
    awaykened  commented on Sept. 18, 2015, 10:02 p.m. edit 4

    how do you solve this

    seriously i have no intention of buying Cindy lunch

    Edit: yay~

    Edit: NO WTF OVER FIVE MINUTES