Problem
/*
Given an array of numbers, only one number appears once, others twice. Find the number.
What if two numbers appear once, what if 500 numbers appear once. How to find these numbers.
I know if only one number appears once, we could use xor, but what if more than one?
How to do it efficiently?
*/
Solution
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Find the numbers -- Amazon
Created Date : 01-10-2013
Last Modified :
============================================================================
*/
#include <iostream>
#include <iomanip>
#include <set>
using namespace std;
void FindNums(int* arr, int len, set<int>& s)
{
for(int i = 0; i < len; i ++){
if(s.find(arr[i]) == s.end()){
s.insert(arr[i]);
}
else{
s.erase(arr[i]);
}
}
}
void DoTest(int* arr, int len)
{
cout << "The array is" << endl;
for(int i = 0; i < len; ++i){
cout << setw(4) << arr[i] << " ";
}
cout << endl;
set<int> s;
FindNums(arr, len, s);
cout << "\nThe output is" << endl;
for(auto i: s){
cout << setw(4) << i << " ";
}
cout << endl;
cout << "------------------\n" << endl;
}
int main(int argc, char* argv[])
{
int arr0[] = {0, 1, 1, 2, 2, 3, 3};
DoTest(arr0, sizeof(arr0) / sizeof(arr0[0])); // Expect 0
int arr1[] = {0, 0, 1, 2, 2, 3, 3};
DoTest(arr1, sizeof(arr1) / sizeof(arr1[0])); // Expect 1
int arr2[] = {0, 0, 1, 2, 2, 3};
DoTest(arr2, sizeof(arr2) / sizeof(arr2[0])); // Expect 1, 3
int arr3[] = {0, 0, 1, 2, 3, 4, 4};
DoTest(arr3, sizeof(arr3) / sizeof(arr3[0])); // Expect 1, 2, 3
return 0;
}
Output
The array is
0 1 1 2 2 3 3
The output is
0
------------------
The array is
0 0 1 2 2 3 3
The output is
1
------------------
The array is
0 0 1 2 2 3
The output is
1 3
------------------
The array is
0 0 1 2 3 4 4
The output is
1 2 3
------------------
Press any key to continue . . .