1

In an array except three numbers all numbers occur odd number of times. How to find all three numbers occurring even number of times in an array?

I can get till a point where I have xor of all three even occurring numbers. How to get the three numbers from that xor value? My approach till now:

#include <iostream>
#include <set>
using namespace std;

int main() {
    // Find the 3 numbers occuring even times in an array
    int arr[] = {1,6,2,88,34,4,98,25,61,7,2,78,2,78,8,25,9,34,56,331};
    int a = arr[0];

    for (int i=1;i<20;i++)
         a ^= arr[i];

    set<int> myset;
    myset.insert(arr,arr+20);
    set<int>::iterator it;
    for (it=myset.begin(); it!=myset.end(); ++it)
        a ^= *it;

    cout<<a<<endl; // a stores xor of the three numbers occuring even number of times, i.e., (25^78^34)=117
    return 0;
}

Note: Hashtable and sorting should not be used. The solution should be in O(n) time.

hichris123
  • 10,145
  • 15
  • 56
  • 70
Rajarshi Sarkar
  • 199
  • 2
  • 13
  • Clue here: http://stackoverflow.com/a/9072707/786351 – ElKamina Sep 18 '14 at 07:13
  • @ElKamina>> I have three numbers xored together in a. How to implement this here? – Rajarshi Sarkar Sep 18 '14 at 07:27
  • It is not a big challenge to come up with a solution that performs asymptotically worse than the forbidden hashtable. Sort the array, then count each streak of identical numbers. Done. – n. m. could be an AI Sep 18 '14 at 07:39
  • @n.m.>> Note part updated. – Rajarshi Sarkar Sep 18 '14 at 07:44
  • 1
    Your solution that uses `std::set` is already O(n log n), so you can just as well drop this direction of thought now. Note that the problem is stated incorrectly, as 0 is an even number. Thus any number that does not appear in the array appears an even number of times. There are infinitely many such numbers. – n. m. could be an AI Sep 18 '14 at 07:46
  • If you modify the problem such that it specifies positive and even number of occurrences, I suggest you try an easier one first. Assume there is just one number that occurs a positive and even number of times, can you find it in O(n)? Hint: it was already discussed on stackoverflow, more than once. No satisfactory solution was produced. – n. m. could be an AI Sep 18 '14 at 08:04
  • If hashtable and sorting are not allowed, what's the point of allowing `set`? – Arun Sep 19 '14 at 18:25

2 Answers2

0

The solution of your problem is as

`
#include <iostream>
#include <set>
using namespace std;

int main() {
    // Find the 3 numbers occuring even times in an array
    int arr[] = {1,6,2,88,34,4,98,25,61,7,2,78,2,78,8,25,9,34,56,331};
    set<int> myset;
set<int> myset_final;


    for (int i=1;i<20;i++)
    {
    if(myset.exists(a[i]))
        myset.remove(a[i]);
    else myset.insert(a[i]);
    }
for(int i=0;i<i<20;i++)
{
    if(!myset.exists(a[i]))
        myset_final.insert(a[i]);
}
    //Now the myset_final contains the numbers that are occured even number of times.
return 0;
}
`

This is the best solution according to me but not the O(n) it O(nlog(n)).

Zeshan Khan
  • 294
  • 2
  • 15
  • The answer is formally incorrect as O(n) performance is required. It was downvoted before the question was amended with O(n) requirement, because O(n) requirement is implicit in this question. O(n log n) solutions are (1) trivial and (2) don't even need the "odd", "even" and "3" parts of the problem. One could use "divisible by 7", "indivisible by 7" and "3" instead, or "perfect square", "not perfect square" and "42", or whatever. That's why it's obvious to a trained eye that your solution is not one that is needed or intended, even if it was formally correct at some point. – n. m. could be an AI Sep 18 '14 at 13:57
  • "O(n) requirement is implicit in this question" i could not found it in the problem statement and the requirement i found is only about accurate solution not efficient most solution. – Zeshan Khan Sep 18 '14 at 14:16
  • "Implicit" means it is not physically there, but should be understood as if it's there. The question now says `The solution should be in O(n) time.` so it's explicit. – n. m. could be an AI Sep 18 '14 at 14:33
  • I can retract the downvote but you need to edit the answer (the site requires that). Just mention that it's O(n log n). – n. m. could be an AI Sep 18 '14 at 15:54
0

I found this solution which does the job in O(n) time and O(1) space but the only thing is the numbers of the array can be in range [0,63].

Kushagra Srivastava
  • 381
  • 3
  • 7