Finding Two Numbers That Appear Once in Array of Duplicated Numbers

by Zoran Horvat
February 17, 2014

Problem Statement

An array of integer numbers is given, such that each number appears exactly twice with exception of two numbers which appear once each. Write a function which finds two numbers that appear once.

Example: Suppose that array is 1, 2, 1, 3, 4, 3, 5, 4. All numbers except 2 and 5 appear exactly twice. So the function should return numbers 2 and 5 as the result.

This exercise is similar to Finding a Number That Appears Once in Array of Duplicated Numbers . There is also a variation, with a very interesting solution Finding a Number which Appears Once in Array where All Other Numbers Appear Three Times .

Problem Analysis

In exercise Finding a Number That Appears Once in Array of Duplicated Numbers we have discussed a simple method to isolate one number which appears once when all other elements appear exactly twice. The solution was to XOR all the array elements. Since K XOR K is zero for any integer K, we are sure that all duplicated numbers will zero themselves out. The only number which does not cancel itself is the one which appears once. So the result of the operation is that one number.

However, this solution cannot be applied directly to finding two numbers that appear once each. Suppose that these numbers that appear once are J and K, and all other numbers appear twice. If we decide to XOR all the array's elements, the overall result would actually be J XOR K. Unfortunately, there is no way to extract J and K out of their XOR. But there is one thing that we can do. Since J and K are different, we are sure that J XOR K is different than zero. This information is valuable in sense that we know pieces of information that differ. If we pick up any bit that is 1 in J XOR K, we can use it as a mask to test each element of the array. Obviously, that mask will be the discriminator between J and K - only one of them will have value 1 at that particular position.

Now that we have the mask with exactly one bit set to 1, we can walk through the array once again. But this time we are going to maintain two XORed results. One for numbers that have bit 1 at the mask's position and another for numbers that have bit 0 at that position. In this way, we are sure that all duplicates will go into the same pile. But likewise, we are sure that J and K will go into separate piles. The overall result is that the first XORed result will be equal to J and the second XORed result will be equal to K (or the other way around, but it really doesn't matter).

Below is the pseudocode which solves the problem.

function GetUniqueNumbers(a, n, out j, out k)
    -- a - array of integers
    -- n - number of elements in a
    -- j - on output first unique number
    -- k - on output second unique number
begin

    mask = FindMask(a)
    j = k = 0

    for i = 1 to n
        begin
            if a[i] AND mask = 0 then
                j = j XOR a[i]
            else
                k = k XOR a[i]
        end

end

function FindMask(a, n)
    -- a - array of integer numbers
    -- n - number of elements in a
begin

    combined = 0
    for i = 1 to n
        combined = combined XOR a[i]

    mask = 1
    while combined AND mask = 0
        mask = 2 * mask

    return mask
end

This implementation relies on a helper function FindMask which, as its name implies, calculates appropriate mask which can be used to discriminate J from K.

Implementation

Below is the C# console application which lets the user enter elements of the array and then prints out the two unique numbers.

using System;

namespace TwoNumbersAppearingOnce
{

    public class Program
    {

        static void GetUniqueNumbers(int[] a, out int j, out int k)
        {

            int mask = FindMask(a);

            j = k = 0;

            for (int i = 0; i < a.Length; i++)
                if ((a[i] & mask) == 0)
                    j ^= a[i];
                else
                    k ^= a[i];

        }

        static int FindMask(int[] a)
        {

            int combined = 0;
            for (int i = 0; i < a.Length; i++)
                combined ^= a[i];

            int mask = 1;
            while ((combined & mask) == 0)
                mask <<= 1;

            return mask;

        }

        static void Main(string[] args)
        {

            while (true)
            {

                int[] array = ReadArray();
                if (array.Length == 0)
                    break;

                int j;
                int k;

                GetUniqueNumbers(array, out j, out k);

                Console.WriteLine("Numbers that appear once are {0} and {1}.", j, k);
                Console.WriteLine();

            }

        }

        static int[] ReadArray()
        {

            Console.Write("Enter array elements (ENTER to quit): ");
            string line = Console.ReadLine();
            string[] parts = line.Split(new char[] { ' ' },
                                        StringSplitOptions.RemoveEmptyEntries);

            int[] array = new int[parts.Length];

            for (int i = 0; i < array.Length; i++)
                array[i] = int.Parse(parts[i]);

            return array;

        }
    }
}

Demonstration

When application is run, it produces the following output:

            
Enter array elements (ENTER to quit): 1 2 1 3 4 3 5 4
Numbers that appear once are 2 and 5.

Enter array elements (ENTER to quit): 1 2 1 3 5 3 5 4
Numbers that appear once are 4 and 2.

Enter array elements (ENTER to quit):