Algorithms to Find the Single Number in C++

Given an array of integers, every element appears twice except for one. Find that single one. Your algorithm should have a linear runtime complexity. Implement it without using extra memory.

The linear runtime complexity means we should have a O(n) algorithm, in other words, only one single loop (or multiple single loops). Double, nested loops are not allowed.

I guess the time constraint for this problem is 1 second because at first, my optimised  algorithm is accepted with 832ms running time. Of course it is written in C++ if it is in Java, it will surely get time limit exceeded.

The O(n^2) algorithm

We need first to find out a unique number (integer) that can be used as a flag that indicates if a number has been checked before, so if yes, we can skip it. So, let’s find the minimal number of the list first,

1
2
3
4
5
6

        int min = A[0];
        for (int i = 1; i < n; i ++) {
            if (A[i] < min) {
                min = A[i];
            }
        }

        int min = A[0];
        for (int i = 1; i < n; i ++) {
            if (A[i] < min) {
                min = A[i];
            }
        }

And, we can start increment the number, if this has not been found the list, then we can use this number as a flag.

1
2
3
4
5
6
7
8
9
10
11
12

        int kmin = min + 1;
        do {
            int flag = 0;
            for (int i = 0; i < n; i ++) {
                if (A[i] == kmin) {
                    flag = 1; // we cannot use this number
                    break;
                }
            }
            if (flag == 0) break;
            kmin ++;
        } while (true);

        int kmin = min + 1;
        do {
            int flag = 0;
            for (int i = 0; i < n; i ++) {
                if (A[i] == kmin) {
                    flag = 1; // we cannot use this number
                    break;
                }
            }
            if (flag == 0) break;
            kmin ++;
        } while (true);

Then a normal nested loop can be established obviously, checking current element (if not marked tested, because most numbers appear twice), return the number if it has only appeared once.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

        for (int i = 0; i < n; i ++) {
            if (A[i] == kmin) continue; // has appeared before
            int c = 0;
            int k = A[i];
            A[i] = kmin;
            for (int j = i + 1; j < n; j ++) {
                if (A[j] == k) {
                    c ++;
                    A[j] = kmin; // mark this so to skip next time
                    if (c == 1) break; // maximum twice
                }
            }
            if (c != 1) return k; 
        }

        for (int i = 0; i < n; i ++) {
            if (A[i] == kmin) continue; // has appeared before
            int c = 0;
            int k = A[i];
            A[i] = kmin;
            for (int j = i + 1; j < n; j ++) {
                if (A[j] == k) {
                    c ++;
                    A[j] = kmin; // mark this so to skip next time
                    if (c == 1) break; // maximum twice
                }
            }
            if (c != 1) return k; 
        }

This got accepted in 872ms, clearly not fast enough.

The O(n) algorithm

The algorithm is a bit tricky. We need to use the exclusive OR operation (XOR), The C/C++ operator is ^ (Exclusive OR). The XOR for two identical numbers is zero. So the XOR of all numbers should be the number of that particular number only appeared once. All other numbers will cancel out to zero because there are pairs of equal numbers. The XOR of any number with zero stays the same that is because 1^0 = 1 and 0^0 = 0, 1^1 = 0.

1
2
3
4
5
6
7
8
9

class Solution {
public:
    int singleNumber(int A[], int n) {
        while(--n > 0) { // to reuse the parameter, no additional storage
            A[n - 1] ^= A[n];
        }
        return A[0];
    }
};

class Solution {
public:
    int singleNumber(int A[], int n) {
        while(--n > 0) { // to reuse the parameter, no additional storage
            A[n - 1] ^= A[n];
        }
        return A[0];
    }
};

Oh yeah! We have a AC in only 48ms! (20 times faster!)

Teaching Kids Programming – Find the Single Number in Array

–EOF (The Ultimate Computing & Technology Blog) —