Wear a helmet. Even when coding.

exercises > number-appearing-once-in-array-of-numbers-appearing-three-times

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 low-order bits of the modulo 3 sum, while bits in A represent high-order 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 two-bit number AB, the result of modulo 3 addition operation is given in the following table:

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

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

    a = b = 0

    for i = 1, n
            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’

    return a OR b


Quite an astonishing piece of code when you know how complicated it is to find which number appears exactly once.


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)

            int unique = FindUniqueNumber(a);

            Console.WriteLine("Number appearing once is {0}.", unique);



    static int[] ReadArray()

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

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

        return a;



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 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 long-term maintainability.

Follow him on Twitter @zoranh75 to receive updates and links to new articles.

Watch Zoran's video courses at (requires registration):

Tactical Design Patterns in .NET: Managing Responsibilities

Applying a design pattern to a real-world 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