http://www.codinghelmet.com/ Wear a helmet. Even when coding. Follow Zoran Horvat @zoranh75
exercises > two-numbers-appearing-once-in-array

# Exercise #24: Finding Two Numbers That Appear Once in Array of Duplicated Numbersby Zoran Horvat@zoranh75February 17, 2014

## Problem Statement

An array of integer numbers is given, such that each number appears exactly twice with exception of two numbers which appear once each. Write a function which finds two numbers that appear once.

Example: Suppose that array is 1, 2, 1, 3, 4, 3, 5, 4. All numbers except 2 and 5 appear exactly twice. So the function should return numbers 2 and 5 as the result.

This exercise is similar to Finding a Number That Appears Once in Array of Duplicated Numbers. There is also a variation, with a very interesting solution Finding a Number which Appears Once in Array where All Other Numbers Appear Three Times.

## Problem Analysis

In exercise Finding a Number That Appears Once in Array of Duplicated Numbers we have discussed a simple method to isolate one number which appears once when all other elements appear exactly twice. The solution was to XOR all the array elements. Since K XOR K is zero for any integer K, we are sure that all duplicated numbers will zero themselves out. The only number which does not cancel itself is the one which appears once. So the result of the operation is that one number.

However, this solution cannot be applied directly to finding two numbers that appear once each. Suppose that these numbers that appear once are J and K, and all other numbers appear twice. If we decide to XOR all the array's elements, the overall result would actually be J XOR K. Unfortunately, there is no way to extract J and K out of their XOR. But there is one thing that we can do. Since J and K are different, we are sure that J XOR K is different than zero. This information is valuable in sense that we know pieces of information that differ. If we pick up any bit that is 1 in J XOR K, we can use it as a mask to test each element of the array. Obviously, that mask will be the discriminator between J and K - only one of them will have value 1 at that particular position.

Now that we have the mask with exactly one bit set to 1, we can walk through the array once again. But this time we are going to maintain two XORed results. One for numbers that have bit 1 at the mask's position and another for numbers that have bit 0 at that position. In this way, we are sure that all duplicates will go into the same pile. But likewise, we are sure that J and K will go into separate piles. The overall result is that the first XORed result will be equal to J and the second XORed result will be equal to K (or the other way around, but it really doesn't matter).

Below is the pseudocode which solves the problem.

```function GetUniqueNumbers(a, n, out j, out k)
-- a - array of integers
-- n - number of elements in a
-- j - on output first unique number
-- k - on output second unique number
begin

j = k = 0

for i = 1 to n
begin
if a[i] AND mask = 0 then
j = j XOR a[i]
else
k = k XOR a[i]
end

end

-- a - array of integer numbers
-- n - number of elements in a
begin

combined = 0
for i = 1 to n
combined = combined XOR a[i]

while combined AND mask = 0

end
```

This implementation relies on a helper function FindMask which, as its name implies, calculates appropriate mask which can be used to discriminate J from K.

## Implementation

Below is the C# console application which lets the user enter elements of the array and then prints out the two unique numbers.

```using System;

namespace TwoNumbersAppearingOnce
{

public class Program
{

static void GetUniqueNumbers(int[] a, out int j, out int k)
{

j = k = 0;

for (int i = 0; i < a.Length; i++)
if ((a[i] & mask) == 0)
j ^= a[i];
else
k ^= a[i];

}

{

int combined = 0;
for (int i = 0; i < a.Length; i++)
combined ^= a[i];

while ((combined & mask) == 0)

}

static void Main(string[] args)
{

while (true)
{

if (array.Length == 0)
break;

int j;
int k;

GetUniqueNumbers(array, out j, out k);

Console.WriteLine("Numbers that appear once are {0} and {1}.", j, k);
Console.WriteLine();

}

}

{

Console.Write("Enter array elements (ENTER to quit): ");
string[] parts = line.Split(new char[] { ' ' },
StringSplitOptions.RemoveEmptyEntries);

int[] array = new int[parts.Length];

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

return array;

}
}
}
```

## Demonstration

When application is run, it produces the following output:

```Enter array elements (ENTER to quit): 1 2 1 3 4 3 5 4
Numbers that appear once are 2 and 5.

Enter array elements (ENTER to quit): 1 2 1 3 5 3 5 4
Numbers that appear once are 4 and 2.

Enter array elements (ENTER to quit):
```

Published: Feb 17, 2014; Modified: Apr 3, 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.

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

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