What's an efficient algorithm to find one unique number in a set of 1 millions numbers? [closed]

Question

I have been asked this question in an interview. In 1 million numbers, all numbers have a duplicate except for one number. How to find that one number? Which algorithm should I use to get a good time and space complexity? I got an idea to use EXOR gate but I'm still lagging in deploying that.

Answer 1

Use xor for all numbers sequentially.

For following list of numbers:

1, 2, 3, 4, 3, 2, 1

Let ^ represents the exclusive disjunction (or xor)

Then,
1 ^ 2 ^ 3 ^ 4 ^ 3 ^ 2 ^ 1 = 4

Answer 2

Another simple solution: Two bitsets can be used, one for marking the existance of a number and another to mark duplication. We iterate through the array amd mark each element for existence and duplication. Then we iterate through the bitsets to find a number that is marked for existence and but not marked for duplication.

int[] numbers = new int[] { 1, 1, 2, 2, 3, 4, 4, 5, 5 };

    BitSet bs1 = new BitSet();
    BitSet bs2 = new BitSet();

    int largestNumber = 0;

    for (int i = 0; i < numbers.length; i++) {
        int number = numbers[i];
        if (bs1.get(number) == false) {
            // Mark for existence
            bs1.set(number);
        } else {
            // Mark for duplicating
            bs2.set(number);
        }

        if (number > largestNumber) {
            largestNumber = number;
        }
    }

    for (int i = 0; i <= largestNumber; i++) {
        if (bs1.get(i) && !bs2.get(i)) {
            System.out.println("Non duplicating number is:  " + i);
        }
    }

}

Answer 3

try this

    int[] a = {1, 2, 1, 2, 3};
    Arrays.sort(a);
    for(int i = 0; i < a.length; i++) {
        if (i == 0 && a[i] != a[i + 1] || i == a.length -1 || a[i] != a[i - 1] && a[i] != a[i + 1]) {
            System.out.println(a[i]);
            break;
        }
    }