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

If you wish to learn more, please watch my latest video courses

This course begins with examination of a realistic application, which is poorly factored and doesn't incorporate design patterns. It is nearly impossible to maintain and develop this application further, due to its poor structure and design.

As demonstration after demonstration will unfold, we will refactor this entire application, fitting many design patterns into place almost without effort. By the end of the course, you will know how code refactoring and design patterns can operate together, and help each other create great design.

More...

In four and a half hours of this course, you will learn how to control design of classes, design of complex algorithms, and how to recognize and implement data structures.

After completing this course, you will know how to develop a large and complex domain model, which you will be able to maintain and extend further. And, not to forget, the model you develop in this way will be correct and free of bugs.

More...

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.

- Favoring Object-oriented over Procedural Code: A Motivational Example
- From Dispose Pattern to Auto-disposable Objects in .NET
- What Makes Functional and Object-oriented Programming Equal
- Overcoming the Limitations of Constructors
- Does the Command Pattern Require Undo?
- What Makes while Loop a Poor Choice in Programming
- More...

- Refactoring to Design Patterns
- Mastering Iterative Object-oriented Programming in C#
- Making Your C# Code More Object-oriented
- Making Your C# Code More Functional
- Making Your Java Code More Object-oriented
- 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