2

An integer array is given. In that array, 3 unique numbers have number of occurrence as even. Rest have only one occurrence. Is there any way to find those numbers using XOR logic. Also the given array is of n+3 elements. All elements of the array are in range 1 to n.

for eg: arr= {4, 2, 4, 5, 2, 3, 1, 5} where n = 5 here unique numbers with even occurrence are 2, 4 and 5

I did the XOR of array numbers along with xor of range 1 to n. That gave a number which is the answer of XOR of final three unique numbers. In case of two numbers we can check the set bit and proceed to find the numbers. But what about three numbers. Is there any way to do this.

I know hashing can be used to solve the problem. I am looking for XOR approach to solve the problem.

MrTambourineMan
  • 1,025
  • 1
  • 11
  • 19
  • 1
    I think you can use [this answer to very similar question](http://stackoverflow.com/a/3010534/1009831). It gives linear time O(1) space (with constant array) algorithm with nice explanation. – Evgeny Kluev Nov 24 '14 at 20:03
  • yes I think little modification of that approach should work. Will try – MrTambourineMan Nov 24 '14 at 20:06

1 Answers1

-1

Xor can help you because: 

XOR (Exclusive Or) truth table:
           A    B   XOR
           0    0    0
           1    0    1
           0    1    1
           1    1    0

So what you can do is:

A. Divide the elements that are occurring more than ones to sets
   of the same value 
B. Then xor all elements in each of those sets
C. If the result is zero than you can return that element to the end set

If you want only 3 numbers than when the previous set is of size three you can return it but you can use this logic to calculate any even number of elements in a group.

sivi
  • 10,654
  • 2
  • 52
  • 51
  • By Step A, do you mean creating separate bucket for each number? It looks like hashing. – MrTambourineMan Nov 24 '14 at 15:06
  • {{4,4},{5,5},{2,2},{1},{3}} no need to hash on such small data just use a data structure that allow groups repetition maybe int Array. Set does not allow repetition sometimes. this one do. array of arrays will work here – sivi Nov 24 '14 at 15:10
  • You are using extra data structure which can be of the order n (space complexity). That is the same case like using hashing. – MrTambourineMan Nov 24 '14 at 15:23
  • this is not hashing hashing is when you use key to value. This is NOT hashing and is using XOR. If you want to solve it with xoring like bit manipulation it is OK. but bit manipulation and xor are not the same thing so it is hard to understand what you wanted. my answer did not use hashing. – sivi Nov 24 '14 at 17:45
  • Instead of that you could have very well used 'count' here. Anyways your solution is using some data structure (whatever you want to call it) which will store data corresponding to every group. XOR's potential is hardly used here. Anyways I think there exist better solution using only XOR and O(1) space complexity. – MrTambourineMan Nov 24 '14 at 19:21
  • Only thing is we have to extend the approach used for two elements so that it can be used for three elements. Just unable to figure out how. – MrTambourineMan Nov 24 '14 at 19:22