http://www.codinghelmet.com/  

Wear a helmet. Even when coding.

exercises > numbers-appear-once-in-unsorted-array

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 object-oriented and functional design, design patterns, writing unit and integration tests and applying methods to improve code design and long-term maintainability.

Follow him on Twitter @zoranh75 to receive updates and links to new articles.

Watch Zoran's video courses at pluralsight.com (requires registration):

Making Your C# Code More Object-Oriented

This course will help leverage your conceptual understanding to produce proper object-oriented code, where objects will completely replace procedural code for the sake of flexibility and maintainability. More...

Advanced Defensive Programming Techniques

This course will lead you step by step through the process of developing defensive design practices, which can substitute common defensive coding, for the better of software design and implementation. More...

Tactical Design Patterns in .NET: Creating Objects

This course sheds light on issues that arise when implementing creational design patterns and then provides practical solutions that will make our code easier to write and more stable when running. More...

Tactical Design Patterns in .NET: Managing Responsibilities

Applying a design pattern to a real-world problem is not as straight-forward as literature implicitly tells us. It is a more engaged process. This course gives an insight to 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...

Writing Highly Maintainable Unit Tests

This course will teach you how to develop maintainable and sustainable tests as your production code grows and develops. 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

webmasters