Exercise #27: Finding Numbers Which Appear Once in an Unsorted Array by Zoran Horvat @zoranh75
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):
See also:
Published: Mar 17, 2014
ZORAN HORVAT Zoran is software architect dedicated to clean design and CTO in a growing software company. Since 2014 Zoran is an author at Pluralsight where he is preparing a series of courses on design patterns, writing unit and integration tests and applying methods to improve code design and longterm maintainability. Follow him on Twitter @zoranh75 to receive updates and links to new articles. Watch Zoran's video courses at pluralsight.com (requires registration): Tactical Design Patterns in .NET: Managing Responsibilities Applying a design pattern to a realworld problem is not as straightforward as literature implicitly tells us. It is a more engaged process. This course gives an insight into tactical decisions we need to make when applying design patterns that have to do with separating and implementing class responsibilities. More... Tactical Design Patterns in .NET: Control Flow Improve your skills in writing simpler and safer code by applying coding practices and design patterns that are affecting control flow. More... Improving Testability Through Design This course tackles the issues of designing a complex application so that it can be covered with high quality tests. More... Share this article
