The Odd Number

View as PDF

Submit solution

All submissions

Best submissions

Points: 7

Time limit: 0.3s

C# 0.5s

JavaScript 0.5s

Memory limit: 2M

C# 37M

Haskell 5M

JavaScript 15M

Perl 6M

PyPy 2 10M

PyPy 3 11M

Python 2 10M

Python 3 11M

Author:

ImbaCalvin

Problem type

Cindy has challenged Weiwei with 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$ ~N~ integers. Out of all $N$ ~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$ ~N~ $(1 \le N \le 10^6)$ ~(1 \le N \le 10^6)~.

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

In the given multiset, exactly one integer will appear an odd number of times, and every other integer will appear an even number of times.

Output Specification

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

Sample Input

Sample Output

Comments

-3

gavin_chen commented on May 21, 2022, 8:10 p.m.

if you want 5/7 of the points just submit your code but to COCI '14 Contest 2 #2 Utrka

0

Xiang_li commented on June 30, 2021, 2:54 p.m.

I need the answer for c++. I can't solve it without a MLE. Where can I find the answer?

1

Plasmatic commented on June 30, 2021, 3:58 p.m. ← edited →

You can ask for help on discord

-8

nowayitstony commented on Jan. 26, 2021, 10:38 p.m.

Bruh there's zero AC python submissions. Author needs to check on that.

This comment is hidden due to too much negative feedback. Show it anyway.

12

GeeTransit commented on Jan. 27, 2021, 1:24 a.m.

Bruh https://dmoj.ca/problem/odd/submissions/?status=AC&language=PY2&language=PY3&language=PYPY&language=PYPY3

2

c commented on July 13, 2020, 4:36 a.m. ← edit 2 →

If the programming language you use takes more than 3 MB of ram to start and does not have a custom memory limit, feel free to open up a ticket.

Note that Python users should use the CPython interpreter instead of PyPy.

1

SagarSaha commented on July 12, 2020, 5:34 p.m.

what if n is 2?

-6

chika commented on July 12, 2020, 6:33 p.m.

You may assume that the input fits the input specification, so a valid test case where $N = 2$ ~N = 2~ is fair game.

This comment is hidden due to too much negative feedback. Show it anyway.

0

SagarSaha commented on July 14, 2020, 3:51 a.m.

But what's gonna be the output?

1
chika commented on July 14, 2020, 4:30 a.m.
Per the problem statement, the integer that appeared an odd number of times.

Note that your program can have undefined behavior on test cases that do not respect the input specification. Consider the following test case:

2 0 0

Your program can do anything when run on this test case - for example, it can crash or go into an infinite loop. It only needs to have the correct behavior on valid test cases.

-18

666245 commented on July 12, 2020, 4:09 a.m. ← edited →

heehee still passed with map 🤭

why am I getting downvoted? I literally pointed out an issue with this problem. T O X I C

This comment is hidden due to too much negative feedback. Show it anyway.

3

maxcruickshanks commented on July 12, 2020, 7:05 p.m. ← edited →

You have never made a submission that passed with a map to this problem; are you referring to someone else who passed with a map? If so, could you link their submission?

-7

666245 commented on July 12, 2020, 10:49 p.m.

I believe the constraints of the problem has changed. The ML used to be 4M

This comment is hidden due to too much negative feedback. Show it anyway.

1

maxcruickshanks commented on July 13, 2020, 12:28 a.m.

Are you saying you could have theoretically passed with a map (i.e., no one has passed with a map)?

-10

666245 commented on July 13, 2020, 12:50 a.m. ← edited →

When the memory limit was 4M, multiple people passed. I would not have made the comment otherwise.

Think about it :)

This comment is hidden due to too much negative feedback. Show it anyway.

6

ScriptKitty commented on July 17, 2018, 9: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

6

injust commented on July 17, 2018, 10: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, 6: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, 6:56 p.m.

Java outofmemory error?

5

Kirito commented on Aug. 16, 2017, 9:09 p.m.

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

1

Daniel_Weintraub commented on Dec. 25, 2015, 2:34 a.m.

Just wondering if this question is possible in Python?

-1

Xyene commented on Dec. 25, 2015, 2:35 a.m.

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

1

aeternalis1 commented on July 18, 2017, 2:54 a.m. ← edited →

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.

-7
Daniel_Weintraub commented on Dec. 25, 2015, 2:50 a.m. ← edited →
for i in range(int(input())): myInput = input() print(1)

This code brings up a TLE. Is this something wrong with the judge?
This comment is hidden due to too much negative feedback. Show it anyway.

5

kobortor commented on Sept. 20, 2015, 4:06 a.m.

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

7

Xyene commented on Sept. 20, 2015, 2:08 p.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.

3

bobhob314 commented on Sept. 19, 2015, 11: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. 30, 2015, 3:16 a.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.

-17

NT_AUTHORITY_SYSTEM commented on Aug. 9, 2017, 2:00 a.m.

That's the wrong algorithm for this one. This one you can just XOR all the numbers together, but for the other one the strings are too large to fit even in a long long.

This comment is hidden due to too much negative feedback. Show it anyway.

5

bruce commented on Sept. 19, 2015, 5:43 p.m.

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

23

awaykened commented on Sept. 19, 2015, 2:02 a.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