Exercise #25: Finding a Number which Appears Once in Array where All Other
Numbers Appear Three Times by Zoran Horvat @zoranh75
Problem Statement
An array of integers is given, such that each number appears exactly three
times in it with exception of one number which appears only once. Write a
function returning number which appears once in the array.
Example: Suppose that array consists of numbers 2, 4, 5, 1, 1, 4, 1, 2, 3, 5,
5, 4, 2. The function should return value 3, because that is the number which
appears only once. All other numbers appear three times.
For similar problem, please refer to exercise Finding a Number That Appears Once in Array of Duplicated Numbers.
Another variation of the problem is covered in exercise Finding Two Numbers That Appear Once in Array of Duplicated Numbers.
Problem Analysis
This problem resembles a similar problem where all numbers appear exactly
twice, except one which appears once. Solution to this problem is explained in
exercise Finding a Number That Appears Once in Array of Duplicated Numbers. Although solution is not directly applicable to problem were numbers appear
three times each, we can still make use of it.
Suppose that we can isolate one particular bit in each of the numbers in the
array. Now we can add values of that bit in all numbers and see whether the
result is divisible by 3 or not. This test tells us about the number which
appears once, because all other numbers either contribute with value 3 or with
value 0. If sum is divisible with 3, then this bit in the number which appears
once must be 0; otherwise it must be 1.
We can now proceed towards solving the problem by making modulo 3 sums for each
of the bits in numbers in the array. But since summation modulo 3 has greatest
value 2, it is obvious that intermediate results cannot be stored in one bit
each. One efficient way is to keep intermediate sums in a pair of bits for each
bit in the number. Alternative, we could use two integer numbers A and B, such that bits in B represent loworder bits of the modulo 3 sum, while bits in A represent highorder bits of the modulo 3 sum.
The operation then proceeds by analyzing what bitwise operations should be
applied so that digits in base 3 represented by bits of A and B really resemble modulo 3 addition results. Suppose that A and B are just one bit long. In that case, when digit K (0 or 1) is added to twobit number AB, the result of modulo 3 addition operation is given in the following table:
Values X in the output indicates values that are not important because inputs can never
be reached in normal operation – namely, intermediate result can never be 11
(binary), which is 3 decimal because we are performing modulo 3 addition. To
extract closed form functions for new A and B, we will use Karnaugh maps.
These expressions will give us the way to combine bits from all numbers in the
array. Finally, each bit in the result which corresponds to AB=00 will be zero, otherwise 1. So, resulting number is just A OR B. Below is the pseudocode which implements this algorithm. Note that all
Boolean operations in the code are bitwise operations.
function FindUniqueNumber(v, n)
 v – array of integers
 n – number of elements in a
begin
a = b = 0
for i = 1, n
begin
a’ = (a AND NOT v[i]) OR (b AND v[i])
b = (b AND NOT v[i]) OR (NOT a AND NOT b AND v[i])
a = a’
end
return a OR b
end
Quite an astonishing piece of code when you know how complicated it is to find
which number appears exactly once.
Implementation
Below is the C# console application which lets the user enter array of integers
and then prints the number which appears once in the array.
using System;
class Program
{
static int FindUniqueNumber(int[] array)
{
int a = 0;
int b = 0;
for (int i = 0; i < array.Length; i++)
{
int a1 = (a & ~array[i])  (b & array[i]);
b = (b & ~array[i])  (~a & ~b & array[i]);
a = a1;
}
return a  b;
}
static void Main()
{
while (true)
{
int[] a = ReadArray();
if (a.Length == 0)
break;
int unique = FindUniqueNumber(a);
Console.WriteLine("Number appearing once is {0}.", unique);
Console.WriteLine();
}
}
static int[] ReadArray()
{
Console.WriteLine("Enter array (ENTER to quit):");
string line = Console.ReadLine();
string[] parts = line.Split(new char[] { ' ' },
StringSplitOptions.RemoveEmptyEntries);
int[] a = new int[parts.Length];
for (int i = 0; i < a.Length; i++)
a[i] = int.Parse(parts[i]);
return a;
}
}
Demonstration
When application above is run, it produces output like this:
Enter array (ENTER to quit):
2 4 5 1 1 4 1 2 3 5 5 4 2
Number appearing once is 3.
Enter array (ENTER to quit):
3 8 5 6 2 8 6 4 7 9 7 6 5 9 1 5 9 4 3 3 1 1 7 8 4
Number appearing once is 2.
Enter array (ENTER to quit):
See also:
Published: Feb 18, 2014; Modified: Apr 4, 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
