1

Possible Duplicate:
Find integer not occurring twice in an array
Accenture interview question - find the only unpaired element in the array

Given an array of integers of odd size. All the integers in the array appear twice except for a single integer. How to find this uncoupled integer in most efficient (both memory and complexity-wise) way?

Community
  • 1
  • 1
aviad
  • 8,229
  • 9
  • 50
  • 98

2 Answers2

14

If you XOR all of them together, you'll end up with the lone (uncoupled) value.

That's because x XOR x is zero for all x values, and 0 XOR x is x.

By way of example, the following program outputs 99:

#include <stdio.h>
int main (void) {
    int num[] = { 1, 2, 3, 4, 5, 99, 1, 2, 3, 4, 5};
    unsigned int i;
    int accum;

    for (accum = 0, i = 0; i < sizeof(num)/sizeof(*num); i++)
        accum ^= num[i];

    printf ("%d\n", accum);

    return 0;
}

In terms of efficiency, it's basically O(1) space and O(n) time complexity, minimal, average and worst case.

paxdiablo
  • 854,327
  • 234
  • 1,573
  • 1,953
1

As pax suggests, XOR'ing all the elements together will give you your lone value.

int getUncoupled(int *values, int len)
{
    int uncoupled = 0;
    for(int i = 0; i < len; i++)
        uncoupled ^= values[i];
    return uncoupled;
}

However there is a slight caveat here: What's the difference between no uncoupled values and a set whose uncoupled value is zero? x^x^y^y = 0 but doesn't x^x^0^y^y also equal zero? Food for thought :)

Jason Larke
  • 5,289
  • 25
  • 28
  • 1
    There's no difference in the output but, given that the specs "odd size" and "all the integers in the array appear twice except for a single integer", `x^x^y^y` is impossible. – paxdiablo Apr 12 '12 at 06:06
  • My mistake, I more meant if the array wasn't odd-sized. Given that it's a question constraint, I guess me pointing that out was irrelevant. – Jason Larke Apr 12 '12 at 06:13