//blame: shardy@@differentchairs.com


#include <stdio.h>
#include <map>
//
// find a value in the given list that occurs an odd number of times
//
//  (return defVal if no match found)
//
int findOddCount(int *val, int valSize, int defVal=-1)
{
        using namespace std;
        map<int,int> bucket;
        for (int i=0; i<valSize; i++) {
            bucket[val[i]]++;
            }
        for (map<int,int>::iterator ii=bucket.begin();ii!=bucket.end();++ii) {
            if ((*ii).second % 2) {
                return (*ii).first;
                }
            }
        return defVal;
}

//
// another approach... (sort, then scan)
// O(nlogn + n)
//
int findOddCount2(int *val, int valSize, int defVal=-1)
{
    std::vector<int> v(val, val+valSize);
    std::sort(v.begin(), v.end());
    int valct = 0;
    int oldval = 0;

    for (size_t i=0; i<v.size(); ++i) {
        if (v[i] != oldval) {
            if (valct%2)
                return oldval;
            oldval=v[i];
            valct=1;
        }
        else
            valct++;
    }
    return defVal;
}

//
// this approach (sort, then bsearch) presumes no more than one oddCount.
// O(nlogn) for the sort, then O(logn) to find the value
//
int findOddCount3(int *val, int valSize, int defVal=-1)
{
    std::vector<int> v(val, val+valSize);
    std::sort(v.begin(), v.end());
    int valct = 0;
    int oldval = 0;

    int lwr=0;
    int upr=valSize;
    // find last boundary between values that's on even index
    while (lwr<upr) {
        int mid = lwr + (upr-lwr)/2;
        int thisval=v[mid];
        int beg;
        for (beg=mid-1; beg>=0 && v[beg]==thisval; --beg)
            ;
        if (beg>0 && !beg%2)
            upr = beg+1;
        else {
            int end;
            for (end=mid+1; end<upr && v[end]==thisval; ++end)
                ;
            if (end%2)
                return thisval;
            lwr = end;
        }
    }
    return defVal;
}

int main(int /*argc*/, char* /*argv*/[])
{
        int a1[]= {1,1,2,2,3,3,4,4,5,5,6,7,7,7,7};
        int a2[]= {10,10,7,7,6,6, 2,2,3,3,4,4,5,5,6,7,7,7,7,10,10};
        int a3[]= {6,6,10,10,7,7,6,6, 2,2,3,3,4,4,5,5,6,7,7,7,7,10,10};
        int a4[]= {10,10,7,7, 2,2,3,3,4,4,5,5,7,7,7,7,10,10,6};
        int a5[]= {6,6};
        int a6[]= {1};
        printf("odd value in a1 is %d\n",
                findOddCount(a1,sizeof(a1)/sizeof(*a1) ));
        printf("odd value in a2 is %d\n",
                findOddCount(a2,sizeof(a2)/sizeof(*a2) ));
        printf("odd value in a3 is %d\n",
                findOddCount(a3,sizeof(a3)/sizeof(*a3) ));
        printf("odd value in a4 is %d\n",
                findOddCount(a4,sizeof(a4)/sizeof(*a4) ));
        printf("odd value in a5 is %d\n",
                findOddCount(a5,sizeof(a5)/sizeof(*a5) ));
        printf("odd value in a6 is %d\n",
                findOddCount(a6,sizeof(a6)/sizeof(*a6) ));
        return 0;
}