by Zoran Horvat

Feb 17, 2014

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.

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
mask = FindMask(a)
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
function FindMask(a, n)
-- a - array of integer numbers
-- n - number of elements in a
begin
combined = 0
for i = 1 to n
combined = combined XOR a[i]
mask = 1
while combined AND mask = 0
mask = 2 * mask
return mask
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.

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)
{
int mask = FindMask(a);
j = k = 0;
for (int i = 0; i < a.Length; i++)
if ((a[i] & mask) == 0)
j ^= a[i];
else
k ^= a[i];
}
static int FindMask(int[] a)
{
int combined = 0;
for (int i = 0; i < a.Length; i++)
combined ^= a[i];
int mask = 1;
while ((combined & mask) == 0)
mask <<= 1;
return mask;
}
static void Main(string[] args)
{
while (true)
{
int[] array = ReadArray();
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();
}
}
static int[] ReadArray()
{
Console.Write("Enter array elements (ENTER to quit): ");
string line = Console.ReadLine();
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;
}
}
}
```

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

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.

- The Fast Pencil Fallacy in Software Development
- 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?
- 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