# Solution to Odd-Occurrences-In-Array by codility

18 Sep

Question Name: Odd-Occurrences-In-Array or OddOccurrencesInArray

This question is completely the same as the Perm-Missing-Elem by codility. The comment from Kim is very helpful.

### 65 Replies to “Solution to Odd-Occurrences-In-Array by codility”

• Fayeeg says:

Brilliant

1. Femi says:

Please could you explain what the ^= operator does in the expression?
Thanks.

2. Mark says:

dosn’t work with [7, 9, 3, 9, 3, 9, 3]

• Mark says:

oh, sorry i’m dosn’t look at condition : “N is an odd integer within the range [1..1,000,000];”

• Sheng says:

That’s fine. Good to see that you catch the bug.

• Breno Gaudereto Oliveira says:

i still didnt got it.. Why A couldnt be [7,9,3,9,3,9,3]? N is 7, so odd and within 1 – 1,000,000…

• Breno Gaudereto Oliveira says:

oh, actually because 9 and 3 are also odd…hehe.. sorry about that.

• Summiya says:

Still don’t get it ?can you please explain?

3. Mayank says:

JavaScript solution
Why I am getting only 11% for correctness?

• Sheng says:

When you are using “for (var number in A)”, you are actually getting the indexes, such as [0, 1, 2, …], rather than the array elements.

• JD says:

You should use:
for (var number of A)

• sam says:

use for each.

4. Davide says:

My Java solution (100%)

• sandeep says:

bro can u explain me one statement in else part “” i = j – 1; “”

• Sheng says:

Right after “i = j – 1”, it goes into for loop and run “i++”. Eventually, for the next iteration, i = j. And we are accessing the first next character that is not A[old i].

• paul says:

O(N^2) complexity

• Yes. It’s O(N).

I just wrote O(NlogN) Code. It can’t solved.

5. dirk says:

• Sheng says:

O(N^2) complexity

6. Ty says:

Iâ€™m quite new to programming but here’s my python solution. I didnâ€™t realise I could have used XOR.

• Sheng says:

Welcome to the coding world ðŸ™‚
Your solution is working. That’s great! And the major improvement space is, it’s abusing the exception mechanism.

• AN says:

HI Sir
Could you please elucidate result ^= number this line of code. I have checked out the PermMissing problem and understood the XOR operation . However, I do not know what ^= will return
Thanks

7. alfredo says:

ruby solution

• MatB says:

all(map(lambda e: e%2, a)) # python built-in style

• MatB says:

errr perhaps I should have read the *actual* question prior to answering.

• nicolai says:

Where can you get info on this operator, I canÂ´t find it anywhere. How does it work?

• Sheng says:

Ruby’s built-in operator. I do not have any experience in Ruby. But it looks so.

8. juan says:

Mi Javascript Solution 100%

9. Dean says:

My very simple Java solution (100%).

• Rajasekhar says:

Bro i need explanation

This is my solution in python
I got a 100% score

• Alexey says:

Looks correct and have O(N) complexity.

• John says:

It does comply with time complexity, but I think it exceeds space compexlity of O(1)

• Vi says:

if ocurrences[n] % 2 0,
I think we could say:
if ocurrences[n] == 1:
right?

11. Christian says:

Does anyone know what the ^= means? The Perm-Missing-Elem by codility post that keeps being references does not explain this.

• Sheng says:

It’s XOR.

12. Jose Colombia says:

In PHP 100% To All ðŸ˜€

13. Baolin Liu says:

14. Alistait says:

I see lots of solutions that call sort but the standard sorts are comparison sorts and have run time O(N logN). The question asks for O(N). That they pass the test indicates that the system is unable to distinguish O(N) and O(N log N) but I donâ€™t believe they are correct per the instructions.

• Sheng says:

You are totally correct. The solutions with `sort` is not right, because of the time complexity.

15. Sam says:

A ruby solution…

16. andrey says:

I have the following solution:

but have only Correctness 80% because of the error during check:

And this errors occurs everytime…
Can somebody explain what is the issue in my solution?

• Sheng says:

Consider the example [1, 1, 1, 2, 2].

17. Aurelio says:

Another in Python, using set:

• Fantom says:

this is a perfect solution!!!
But it still gave me this:
Detected time complexity:
O(N) or O(N*log(N))

I’m new to python and returned to coding after a long time! what does this mean?

18. FedeDyna says:

Hallo. This is my C++ version. I am not sure, I get 100% but I am wondering if it is 100% bug-proof. I modify the python version of @Ty.

And yes this is O(N logN) . I am wondering if is it possible to obtain something similar to the one of @Ivan Padron .

• Sheng says:

>> catch (exception& e) // I am not sure of this part
It’s used to catch the odd occurrence, when the largest number occurs for odd number of times.

• Thanks for your suggestion. Here is what I wrote on PHP and it gets 100% with Time complexity is O(N) or O(N*log(N)).

19. Leo Vilhena says:

Python 3.6

20. MaryMack says:

Here’s the thing about all the solutions that sort and then iterate through the array. Sorting takes O(nlogn), so even if you are able to iterate through the array a single time to determine the odd occurrence, you will not meet the specified time complexity requirement.

21. ali says:

22. Jeronimo Carrizo says:

Hi, here are my 100 solution.

https://app.codility.com/demo/results/trainingTJGJWC-323/

23. Anubha says:

Possible C++ solution:

24. Suryaprakash Singh says:

here is my 100% test pass but fails in time complexity

25. Efrain says:

This is my solution in C++ I got 100%

26. I hijacked yours for solution in VB since nobody apparently uses it anymore except me. It got 100% so I guess it’s correct. I’m looking to learn Python soon after testing.

27. JT says:

100% with O(N) or O(NlogN)

28. hainp says:

i don’t know why my solution just get 77%
time complexity is O(n**2)

• Sheng says:

I do not know your programming language, and did not debug the code. The idea is correct while inefficient. Also with some optimization, I guess `ar` is unnecessary.

29. Renato Milan dos Santos says:

My 100% java solution:

O(N) or O(N*log(N)) complexity

30. PHP– 100% accurate O(N) or O(N*log(N)) complexity