Exercise #7: Finding a Number That Appears Once in Array of Duplicated Numbers by Zoran Horvat @zoranh75
Problem Statement
An array is given consisting of integer numbers. Each number except one appears
exactly twice. The remaining number appears only once in the array. Write a
function which returns a number which appears only once in the array.
Example: Suppose that array contains values 1, 4, 2, 1, 3, 4, 2. The function
should return value 3, because that it occurs once in the array. Values 1, 2
and 4 occur two times each.
Keywords: Array, duplicate values.
If you are interested in similar exercise, you may read another article in
which we are solving similar problem, with only difference being that there are
two numbers that appear once in the array of duplicated integer numbers. This
exercise can be found on page Finding Two Numbers That Appear Once in Array of Duplicated Numbers.
Problem Analysis
If we suppose that array is sorted, then solution to the problem would be very
simple. We would traverse the array and check successive values in pairs. As
soon as a pair of different values is reached, the first value in the pair is
the one that occurs only once. If end of array is reached, then the last value
in the array is the one we are looking for.
This solution cannot be applied directly because array is not sorted. In order
to sort the array we need O(NlogN) operations. Once the array is sorted,
traversal requires only O(N) steps. But is there a more efficient solution,
such that solves the problem in O(N) steps total without previously sorting the
array?
To find the efficient solution we need to somehow mimic the solution on sorted
array. The key question here is which properties can be attributed to numbers
that appear twice in the array, so that we can eliminate them while traversing
the unsorted array even when those numbers do not appear in successive places.
One such property would be to test parity of each number and to count how many
even and odd numbers there are in the array. In example given in the problem
statement there are total of seven numbers in the array, four of them even and
three of them odd. What can we see from this result? Each odd number having a
pair adds two occurrences to the count of odd elements; the same stands for
even numbers. The one value without a pair, being even or odd in itself, adds
only one to the corresponding count. So from even and odd counts we can figure
out the parity of the solitary element. Having three odd numbers in the example
array, we conclude that requested number must be odd. And really, we are
looking for value 3, which is indeed odd.
This analysis still doesn't lead to the solution, but it is a good
demonstration that some attributes of numbers are preserved during array
traversal even when coinciding numbers are located far away from each others.
We can go with this analysis further  ignoring the parity, we can divide all
numbers by two and then count parities of the resulting numbers. When this
result is combined with parity test, we obtain perfect information about what
is the remainder when requested number is divided by four. Now this starts to
take shape of a solution to the problem.
We can abstract the parity analysis by observing that we do not need to know
exact counts of even and odd values. We only require the information which of
the counts is odd. Even more, if number of odd numbers is odd itself, then the
result is odd as well. Consequently, requested number's parity is equal to
parity of a number obtained by only counting the odd numbers in the array!
Below is the pseudocode which answers the question what is the parity of the
number appearing only once in the array.
a[0..N1]  array containing integer values
parity = 0
for i = 0, N1
if a[i] mod 2 = 1 then
parity = 1  parity
This simple loop produces value 1 if number of odd values in the array is odd,
and value 0 otherwise. In other words, variable parity will contain the parity of the number that appears exactly once in the array.
However, to make better use of this loop, we can perform modulo division and
parity recalculation by using bitwise operations. Remember that modulo 2
division is equal to ANDing the value with mask 1. Conversely, inverting the
parity, i.e. replacing 0 with 1 and vice versa, can be achieved by XORing
current value with mask 1. Remember also that XORing any value with mask 0
leaves the value unchanged. Now that we know all this, the loop above can be
rewritten into more compact form:
parity = 0
for i = 0, N  1
parity = parity XOR (a[i] AND 1)
Both XOR and AND are bitwise rather than Boolean operations. In this way we
have produced a variable parity with lowest bit equal to the lowest bit of the number which should be isolated
from the array. Notice how we have gradually shifted from the parity analysis
into the specter of bitwise operations. These two areas are closely related
because parity of an integer number is indicated by value of its least
significant binary digit. By performing all operations only on the least
significant bit of the parity indicator produces the same result as all the
arithmetic operations that relied on modulo 2 division. These bitwise
operations prove their true value when we ask what is the value of the second
least significant bit of the singular value in the array. This result is
obtained the same as in case of least significant bit, only mask 2 is used to
extract the second lowest bit:
parity1 = 0
for i = 0, N1
parity1 = parity1 XOR (a[i] AND 2)
Two parity bits extracted this far can be combined as simply as parity OR parity1, which now turns into a value equal to the requested number modulo 4. Notice
that the same value can be reached with only one loop, by using a combination
of the two masks  mask with value 3. The reason is simple: having all the
bitwise operations along the route operate on distinct bits in the result,
there is no fear that parity of one bit will affect the observed parity of
another bit.
And this leads to the final solution. If we completely remove the mask, then we
will obtain the loop which simultaneously tracks parities of all bits in the
number which appears only once in the array. When the loop terminates, parity
indicator will have all of its bits equal to corresponding bits in the
requested number. In other words, parity indicator will be the requested number
itself! Here is the final pseudocode:
function Singular(a, N)
value = 0
for i = 0, N1
value = value XOR a[i]
return value
end
Once again, the XOR operation used is the bitwise operation between the two
operands.
Now that we have produced the final solution, we can take a look at it the
other way around. We are simply XORing all the numbers in the array, and that
operation magically produces the number that appears exactly once in the array.
The reason why this method works comes from the fact that all other numbers
appear exactly twice each. And, whenever a number is XORed with itself, value
0 is produced. And when any number is XORed with zero, it remains unchanged.
Therefore, second appearance of any number simply removes the first appearance
of the same number from the cumulative result. What remains in the end is only
the number which doesn't appear the second time and, consequently, could not
score out its first appearance. This explains why the simple loop produced
above works correctly. On a related note, we could start from this short
analysis and come up with exactly the same code for the solution.
Implementation
Now that we have produced the pseudocode which solves the problem, the
corresponding C# function can be written with very little effort:
int Singular(int[] a)
{
int value = 0;
for (int i = 0; i < a.Length; i++)
value = value ^ a[i];
return value;
}
Demonstration
We can use the Singular function to analyze the array given as an example in the problem statement
section:
int[] a = new int[] { 1, 4, 2, 1, 3, 4, 2 };
int s = Singular(a);
Console.WriteLine("Value that appears once is {0}.", s);
This code produces output as expected:
Value that appears once is 3.
FollowUp Exercises
Given the array containing strings rather than integers, can the XORing
technique be applied to find the string which appears once, as opposed to all
other strings that appear exactly twice each? Note that strings are not
necessarily of the same length.
Try to solve modified problem, in which there are two distinct numbers that
appear once each, while all other numbers appear exactly twice each. This
exercise is covered on page Finding Two Numbers That Appear Once in Array of Duplicated Numbers.
See also:
Published: May 5, 2013; Modified: Feb 17, 2014
ZORAN HORVAT Zoran is software architect dedicated to clean design and team lead in a growing software company. Follow him on Twitter @zoranh75 to receive updates and links to new articles. Watch Zoran's video course Improving Testability Through Design on Pluralsight. Share this article
