by Zoran Horvat

Mar 17, 2014

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.

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
```

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();
}
}
}
```

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):
```

Zoran Horvat is the Principal Consultant at Coding Helmet, speaker and author of 100+ articles, and independent trainer on .NET technology stack. He can often be found speaking at conferences and user groups, promoting object-oriented development style and clean coding practices and techniques that improve longevity of complex business applications.

- What Makes while Loop a Poor Choice in Programming
- How to Wrap System.Random Into an Infinite IEnumerable<int> Sequence
- Substituting the Builder with the Sequence of Factory Methods
- Custom Implementation of the Option/Maybe Type in C#
- Pros and Cons of Multiple Constructors
- Defensive Design: An Experiment
- More...

- Making Your C# Code More Object-oriented
- Making Your C# Code More Functional
- Writing Purely Functional Code in C#
- Tactical Design Patterns in .NET: Creating Objects
- Tactical Design Patterns in .NET: Control Flow
- Tactical Design Patterns in .NET: Managing Responsibilities
- Advanced Defensive Programming Techniques
- Writing Highly Maintainable Unit Tests
- Improving Testability Through Design