Finding Numbers Which Appear Once in an Unsorted Array

by Zoran Horvat
March 17, 2014

Problem Statement

An unsorted array of integer numbers is given. Some numbers may appear multiple times, not necessarily in consecutive locations. Write a function which returns numbers from the array that appear exactly once.

Example: Suppose that the following array has been passed to the function: 2, 4, 6, 3, 2, 5, 1, 4, 5. In this case, function should return array with numbers 6, 3 and 1, in any order.

Problem Analysis

The fact that input array is not sorted complicates the matter. In exercise Finding a Number That Appears Once in Array of Duplicated Numbers we could capitalize on additional information about contents of the array and come up with a creative solution which runs in O(N) time. In exercise Finding a Number which Appears Once in Array where All Other Numbers Appear Three Times we repeated the process, coming up with even more extravagant, but still extremely efficient O(N) solution.

But in this exercise we do not have the benefit of knowing the structure of the array. This has a consequence that same numbers may be located far from each other. It would be beneficial if we could force the same numbers to get next to each other, in which case we could easily identify them. This looks a lot like sorting, which leads to the following idea.

We can apply a slightly modified Quicksort algorithm to the array. As in the original algorithm, we would pick up a convenient pivot and then partition the array around it. Lower range of elements would be strictly smaller than the pivot. Upper range would be populated by elements strictly greater than the pivot. One or more locations in between would then be reserved for elements that are equal to the pivot. And this last sentence is the key to the solution. If there is exactly one occurrence of the pivot in the array, then the pivot is pushed to the output. Otherwise, pivot is silently skipped. In either case, the algorithm is recursively applied to the left and the right part of the array, provided that they are not empty.

The algorithm just described is very similar to Quicksort. The only difference is the additional operation after partitioning the array, when occurrences of the pivot are counted. Quicksort has no interest in counting the pivot, but in our case that is the central operation as it actually identifies numbers that appear exactly once.

So here is the pseudocode of the function which returns unique elements of the array. It is based on a recursive call to a more detailed function.

function UniqueElements(a, n)
    -- a - unsorted array
    -- n - length of the array
begin
    return UniqueRecursive(a, 1, n)
end

function UniqueRecursive(a, lower, upper)
    -- a - partially sorted array
    -- lower - first index to consider
    -- upper - last index to consider
begin

    unique - empty array

    -- In practice apply some more reliable method,
    -- such as Median of Medians, etc.
    pivot = a[lower]

    Partition(a, lower, upper, pivot, out pivotPos, out pivotCount)

    if pivotCount = 1 then
        append pivot to unique

    if pivotPos > lower then
        begin
            subsolution = UniqueRecursive(a, lower, pivotPos - 1)
            append subsolution to unique
        end

    if pivotPos + pivotCount <= upper then
        begin
            subsolution = UniqueRecursive(a, pivotPos + pivotCount, upper)
            append subsolution to unique
        end
    return unique

end

function Partition(a, lower, upper, pivot, out pivotPos, out pivotCount)
    -- a - partially sorted array
    -- lower - index from which to start partitioning
    -- upper - index where to end partitioning
    -- pivot - value around which to partition
    -- pivotPos - on output location of first pivot occurrence
    -- pivotCount - number of appearances of the pivot
begin

    i = lower

    while i <= upper
        begin
            if a[i] < pivot then
                a[lower] = a[i]
                lower = lower + 1
                i = i + 1
            else if a[i] > pivot then
                swap a[upper] and a[i]
                upper = upper - 1
            else
                i = i + 1
        end

    pivotPos = lower
    pivotCount = upper - lower + 1

    for i = lower to upper
        a[i] = pivot

end

Implementation

Code below is a C# console application which implements the function for extracting unique numbers from an unsorted array.

using System;
using System.Collections.Generic;

namespace UniqueNumbers
{

    class Program
    {

        static int[] FindUnique(int[] array)
        {
            return UniqueRecursive(array, 0, array.Length - 1);
        }

        static int[] UniqueRecursive(int[] array, int lower, int upper)
        {

            List<int> unique = new List<int>();

            int pivot = FindPivot(array, lower, upper);

            int pivotPos = 0;
            int pivotCount = 0;
            Partition(array, lower, upper, pivot, out pivotPos, out pivotCount);

            if (pivotCount == 1)
                unique.Add(pivot);

            if (pivotPos > lower)
            {
                int[] subsolution = UniqueRecursive(array, lower, pivotPos - 1);
                unique.AddRange(subsolution);
            }

            if (pivotPos + pivotCount <= upper)
            {
                int[] subsolution = UniqueRecursive(array, pivotPos + pivotCount, upper);
                unique.AddRange(subsolution);
            }

            return unique.ToArray();

        }

        static int FindPivot(int[] array, int lower, int upper)
        {
            return array[lower];
        }

        static void Partition(int[] array, int lower, int upper, int pivot,
                              out int pivotPos, out int pivotCount)
        {

            int i = lower;

            while (i <= upper)
            {
                if (array[i] < pivot)
                {
                    array[lower++] = array[i++];
                }
                else if (array[i] > pivot)
                {
                    int tmp = array[upper];
                    array[upper] = array[i];
                    array[i] = tmp;
                    upper--;
                }
                else
                {
                    i++;
                }
            }

            pivotPos = lower;
            pivotCount = upper - lower + 1;

            for (i = lower; i <= upper; i++)
                array[i] = pivot;

        }

        static void Main()
        {
            while (true)
            {

                int[] array = ReadArray();

                if (array.Length == 0)
                    break;

                int[] unique = FindUnique(array);

                PrintUnique(unique);
            }
        }

        static int[] ReadArray()
        {

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

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

            return array;

        }

        private static void PrintUnique(int[] unique)
        {
            Console.Write("Unique numbers:");
            for (int i = 0; i < unique.Length; i++)
                Console.Write(" {0}", unique[i]);
            Console.WriteLine();
            Console.WriteLine();
        }

    }

}

Demonstration

When application above is run, it produces the following output:

            
Enter numbers (ENTER to exit): 2 4 6 3 2 5 1 4 5
Unique numbers: 1 3 6

Enter numbers (ENTER to exit): 99 50 43 1 10 50 77 13
13 99 47 79 93 4 77 47 18 15 37 76 80 32 65 73 0 54 24
1 16 89 65 59 56 72 83 8 12 66 35 64 74 65 70 56 84 90
13 16 25 46 68 74 0 50 5 57 11 70 31 56 39 65 67 42 81
19 0 54 35 77 70 51 29 17 91 89 1 81 66 40 6 19 41 77
8 63 56
Unique numbers: 43 4 6 5 12 11 10 15 17 18 42 39 31 24
29 25 32 37 40 41 46 90 84 51 57 64 59 63 67 68 72 73
80 76 79 83 93 91

Enter numbers (ENTER to exit):