Exercise #24: Finding Two Numbers That Appear Once in Array of Duplicated
Numbers by Zoran Horvat @zoranh75 February 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
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.
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)
{
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;
}
}
}
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):
See also:
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 objectoriented and functional design, 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): Making Your C# Code More ObjectOriented This course will help leverage your conceptual understanding to produce proper objectoriented 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 realworld problem is not as straightforward 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
